16bit!

エンジニアじゃなくなっちゃった人が何かを書くブログ

【アルゴリズム】新人女子の書いたコードを直すだけの簡単なお仕事の解説を読んだ

昨年ちょっと話題になっていた、「新人女子の書いたコードを直すだけの簡単なお仕事」
の解説記事が出ていたので読みました。

実行時間の差は996倍以上。オンラインハッカソン最速コードの裏側に迫る! - paiza開発日誌

ちなみに僕がチャレンジ直後に書いた記事はこちら↓

【アルゴリズム】新人女子の書いたコードを直すだけの簡単なお仕事をやってみた - 16bit!

まぁ、やっぱりというか何と言うか、自分はアルゴリズム弱いなぁと感じました。
メモがてら感想と、あとアルゴリズム弱者である僕がSランクとれた、
公式解説とは全然違うソースのアルゴリズム解説をしておきます。

公式解説メモ1:二分探索

リストなどの要素数nが膨大な時に、計算量をO(n)ではなくO(log2 n)にするためによく使われる方法。
確か以前paizaの競合であるCodeIQのアルゴリズム問題でも使われていた。

<参考>
二分探索(2分探索)とは - IT用語辞典 e-Words

既知なので特にメモすることは無し。

公式解説メモ2:しゃくとり法

しゃくとり法なるものを知らなかったので、とりあえずぐぐります。

しゃくとり法 - komiyamの日記
SSSSLIDE

なるほど。

どうやらベースは、ある条件に対して真となる範囲を求めるためのアルゴリズムで、
範囲の始点と終点を表す2つの変数を用意して、
状況に応じてどちらか一方を変更(進めたり戻したり)しながら探すものらしい。

2つの変数(l, k)はどちらも0地点からスタートし、
まずはkを進めながら、偽になったらlを進めるという使い方が基本っぽい。
たぶんこの動きがしゃくとり虫っぽいからしゃくとり法と呼ばれているんだと思う。

何も考えずに全てのlに対してkを全ループさせるとO(n^2)になるのを、
O(n)にできるのがすごい点。

今回のような問題の場合(事前に値段リストが昇順ソートされているとすれば)、
i番目の商品とペアになる商品をリストのk番目に見つけたら、
i+1番目の商品とペアになる商品は、k番目以前にあることは自明なので、
k+1番目以降の要素について計算する必要はない。

したがって、iの初期値を0、kの初期値をnとして、
状況に応じてiを++したりkを--したりしながら、O(n)、要するにループ1回分(!)で、
全てのペアを探すことができる。

ちなみに公式にも書いてありますが、今回のケースはそれぞれの初期値が0,nで、
i,kの動きは縮むだけなので、しゃくとりのイメージは湧かないですが、
名前は本質じゃないので問題ないとのこと*1

というわけで公式解説は、通常ならO(n^2)になっちゃうものを、
O(n)にすることで高速化できますよ。
というものでした。

アルゴリズム弱者のコード晒し

さて、公式解説のメモはここまでで、ここからはコード晒し。

private static List<Integer> priceSetList = new ArrayList<Integer>();

public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	//1行目の読込
	String line = br.readLine();
	String[] readLineArray = line.split(" ");
	final int ITEM_NUM = Integer.parseInt(readLineArray[0]);
	final int DAY_NUM = Integer.parseInt(readLineArray[1]);

	//商品数ループして値段のリストを作る
	List<Integer> priceList = new ArrayList<Integer>();

	for (int i = 0; i < ITEM_NUM; i++) {
		line = br.readLine().trim();
		Integer price = new Integer(Integer.parseInt(line));

		if (price.intValue() <= 999990) {
			priceList.add(price);
		}
	}
	Collections.sort(priceList);
	Collections.reverse(priceList);

	//キャンペーン日数分ループして最近値を求める
	for (int i = 0; i < DAY_NUM; i++) {
		line = br.readLine().trim();
		Integer campPrice = new Integer(Integer.parseInt(line));

		Integer nearestPrice = getNearestPrice(priceList, campPrice);
		System.out.println(nearestPrice);
	}
}

まずはmainから。
流れとしては、

1.とりあえず全件分の値段のリストを作ってソートかけとく(逆順なのがポイント)
2.各キャンペーン価格ごとに最近値を割り出し

という素直な作りです。
ほんとはここで「同じ値段は2つまで」みたいなことをしとくと後の処理が速いのかもしれませんが、
値段リストのばらつき次第なので何とも言えません。
期待値的にはどうなんだろ?値段の範囲と商品数がどれくらいならその処理した方がいいのかな?

また、999,990円より高い商品は他と組み合わせると絶対に1,000,000円を超えてしまうため、
組み合わせでは使えません。
ということで、涙ぐましい努力としてそういう商品はリストに加えていません。

ちなみにフィールドに持ってるpriceSetListは、
「値段の組み合わせとしてあり得る値」を順次追加していくリストです。
キャッシュみたいなもんです。

private static Integer getNearestPrice(List<Integer> priceList, Integer campPrice) {
	int ans = 0;

	if (campPrice.intValue() < 20) {
		return new Integer(0);
	}

	if (priceSetList.contains(campPrice)) {
		return campPrice;
	}

	for (int i = 0; i < priceList.size(); i++) {
		int tmp = priceList.get(i).intValue();

		//1つの値段でキャンペーン価格をオーバーしていたら飛ばす
		if (tmp > (campPrice.intValue() - 10)) {
			continue;
		}

		//1つの値段を固定した上で、キャンペーン価格を下回る最大セット価格を求める
		for (int j = 0; j < priceList.size(); j++) {
			if (i == j) {
				continue;
			}

			int tmp2 = priceList.get(j).intValue();
			int total = tmp + tmp2;
			if (total <= campPrice.intValue()) {
				if (total > ans) {
					ans = total;
				}

				if (!priceSetList.contains(new Integer(ans))) {
					priceSetList.add(new Integer(ans));
				}

				if (ans == campPrice.intValue()) {
					return campPrice;
				}
				break;
			}
		}
	}
	return new Integer(ans);
}

続いて、この問題の肝となる「キャンペーン価格を下回るの値段の組み合わせの最大値」を求めるメソッド。
とりあえずこちらも20円より小さい商品の組み合わせはないので、
その場合は絶対0円という涙ぐましい努力をしてます。

組み合わせの求め方としては基本的には2重ループなので、O(n^2)のクソみたいなアルゴリズムです。
が、「別に全件回さなくても組み合わせは見つけられるよね?」という発想で、
2個目のループは最初に条件を満たす相手が見つかった時点で即抜けできるようになっています。

これは金額が大きい順でループ回しているためです。
ちなみにソートを降順にするよりループを逆順にする方がちょっとだけですが速いはずですが、
逆順ループって読みにくくない?ということでソートを降順にしました。

また、値段の組み合わせを作成したら、都度フィールドのリストにキャッシュします。
これにより、キャンペーン価格が既に作成したことのある値段の場合は、2重ループに入ることなく、

if (priceSetList.contains(campPrice)) {
	return campPrice;
}

ここで見つけられるので、処理の後半になればなるほど1つのキャンペーン価格に対して答えを見つけるまでの時間が短くなります(期待)。

ただ、何でもかんでも突っ込むと逆にキャッシュを検査するだけで大変になるので、
その辺のバランスは大事かもしれません。
今となっては思い出せませんが、値段をキャッシュしてるのがキャンペーン価格を下回った時だけになっているのは、その辺のバランスを考慮した結果なのかも。

とまぁこういう感じで、計算量としてはO(n^2)で本来なら時間オーバーでアウトになるところを、

・ループをなるべく速く抜ける
・求めた組み合わせをキャッシュしておく

ことによって、何とかSランクまで持っていきました。

ただ、これって完全に力技だし、変数や標準偏差次第ではしねるので、
やっぱりアルゴリズムはちゃんと勉強する必要があるなぁと思いました(こなみかん

終わり。

*1:そりゃそうだ