frostar@wiki

メニュー

作ったもの

過去の遺物
TRPG
プログラム
リンク

自分関係

ここのページへのリンクについてはこちら
TRPGのセッション記録とかメインのブログ
生配信チャンネル。プログラム<雑談
気が向いたときにやります
個人的な質問に答えてます。

TRPG系

お世話になっているオンラインセッションサイト
TRPGのことならここ!
IRCサーバなど、お世話になってます。
ネクロニカの支援サイトです。ツール開発やオンセもやっています。

プログラム系

初心者のためのプログラムのページ。WindowsSDKの方についても詳しく書いています。
windowsSDKのテクニックがいろいろ書いてあります。
C++STL(標準テンプレートライブラリ)の日本語版リファレンスです。


更新履歴

取得中です。


新人女子の書いたコードを直すやつ


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問題はここにあります。
要約すると
N D
p_1
p_2
...
p_N
m_1
m_2
...
m_D
という書式の入力が与えられ、それぞれのm_iに対して和がm_iを超えない最大の値になるようにp_jから異なる2個を選択するというものです。

とりあえず私の最終コードは↓みたいな感じ。言語はJavaです。
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  5. import java.util.List;
  6. public class Main {
  7. private static List<Integer> goods;
  8. public static void main(String args[]) throws Exception {
  9. String line = br.readLine();
  10. String[] strs = line.split(" ");
  11. int g_max = Integer.valueOf(strs[0]);
  12. int d_max = Integer.valueOf(strs[1]);
  13. goods = new ArrayList<Integer>(g_max);
  14. int[] targets = new int[d_max];
  15.  
  16. for(int i=0;i<g_max;i++){
  17. goods.add(Integer.parseInt(br.readLine()));
  18. }
  19. Collections.sort(goods);
  20.  
  21. for(int i=0;i<d_max;i++){
  22. System.out.println(calc(Integer.parseInt(br.readLine())));
  23. }
  24. }
  25. static int calc(int target){
  26. if(target/2<goods.get(0))return 0;
  27. int end = goods.size()-1;
  28. if(target/2>=goods.get(end))return goods.get(end)+goods.get(end-1);
  29. int answer=0;
  30. int start=0;
  31.  
  32. while(start<end){
  33. int s=0;
  34. while(goods.get(end)+goods.get(start)>target)end--;
  35. s = goods.get(end)+goods.get(start);
  36. if(s==target){
  37. answer = s;
  38. break;
  39. }
  40. if(answer<s)answer = s;
  41. start++;
  42. }
  43. return answer;
  44. }
  45. }
  46.  
とりあえずmainではそれぞれの値を取得。
与えられたgoods(p_j)をソートしてから、calcメソッドにそれぞれの目標値を渡して計算を行っています。
calcメソッドでは次のようなものは計算を行わなくても解がわかるのでそれを先に判別します。
  • 一番小さいgoodsの要素の値段が目標値の半分以上のとき:0(line.32)
  • 一番大きいgoodsの要素の値段が目標値の半分以下のとき:一番大きいgoodsの要素+二番目に大きいgoodsの要素(line.34)

それ以外の場合はそれぞれの計算を行います。
startとendという2つのindexをそれぞれ0とgoodsの要素数-1で初期化します。
また、中間結果変数answerを0で初期化します。
startの要素とendの要素の和が目標値以下になるまでendをデクリメントしていきます(line.35)。
目標値以下になったら、その合計値を目標値と比較し、等しければその値を答えとして返します。
そうでなければ、変数answerと合計値を比較し、合計値のほうが大きければanswerの値を更新します。
その後、startをインクリメントして、同じ処理をstartとendの大小関係が入れ替わるか等しくなるまで続けます。

startとendはループ中で常にstart<endが成り立っており、goodsがソートされているために
goods[start]<goods[end]が成り立ちます。
また、goods[start]<goods[start+1]も成り立つので、
goods[start]+goods[end]が目標値より大きい場合、
goods[start+1]+goods[end]も必ず目標値より大きくなります。
そのため、goods[start]+goods[end]<目標値が満たされた場合、
次の探索はgoods[start+1]に加算して目標値よりも小さくなるのはgoods[end]よりも小さい要素となるので、
ひとつ前のendより大きい値を探索する必要がなくなり、計算量が削減されます。

このアルゴリズムだとだいたいテストケース1で0.09秒でした。
Java最速は0.06秒らしいのでもっと早い方法があると思います(それともインスタンス生成コストとかをもっと減らしてるのかしら?)。
一応タイムを縮める方法として、目標値以下となる値を見つけるのを二分探索にしたり、マルチスレッドにしてみたりもやってみたのですが、いまいち縮まらなかったですね。