cafelier@SRM

二分探索

23:09 |

みなさま二分探索ってどういう風に考えながらコードを書くのでしょうか、ということがちょっと気になりました。特に実数ではなくて整数のもの。問題：

private int X = 1 以上 9_9999_9999 以下の秘密の整数;
bool query(int x) { return X <= x; }

X を直接読まずに query() 関数を何回か呼び出すことで X を求めなさい。

自分の場合、こう考えながら書いています。

int solve()
{
  int L = 0;            // 条件を満たさないとわかっている数を適当に
  int R = 10_0000_0000; // 条件を満たすとわかっている数を適当に

  // 不変条件: 「常に答えは半開区間 (L, R] の範囲にある」

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング。

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング。（重要なので二回）

  while( R-L > 1 ) // 答えの範囲が整数一つになるまで繰り返し
  {
     int C = (L+R)/2; // 二分探索なので真ん中をとる

     (query(C) ? R : L) = C;
     // (query(C) ? L : R) = C; ではない。(L,R] が答えの範囲なので R が条件満たす方、L が満たさない方
  }

  return R; // 答えは (L,R] にあるのだから L じゃなくて R が答え
}

Topcoderにサブミットした二分探索のコード全部に半開区間の不変条件がコメントで書いてあります。これを念じていないと「ループ終了条件」「どっちの場合にLとRのどっちを更新するんだっけ？」「最後に返す値はどれ？」の３カ所で、USB端子の差し込み方向並に毎回迷ってしまうので。

チャレンジフェーズで他の人のコードを見ていると、違う考え方でコード書いている人が結構多いようなので興味が湧いています。if(query(C)) R=C; else L=C+1; みたいな形の更新式になるコードとか。気になります。

追記：反応集 http://togetter.com/li/331840

TCO12 R2C 500

04:32 |

左下にある点の個数と右下にある点の個数を２パスで数えて３パス目で集計したけれど、１パスでできるなあと気づいて感心して書き直した物。

続きを読む

GCJ12 Round1B A

11:50 |

Dで。普通。

続きを読む

GCJ12 Round1B B

11:50 |

Dで。std.containerの使ったつもりになって書いたはいいがコンパイルエラーとれず使い方わからず、自分で書いた方が速え、という展開に…

続きを読む

GCJ12 Round1B C Small

11:50 |

Dで。3進数マスクすぐ作れるのはいい感じ。Largeわからなかった。

続きを読む

TCO12 Round2A 450

04:04 |

300に泥はまりしすぎて時間かけられなかったせいで焦りすぎて変なtypoを直せず…終了直前にサンプル通せたコードがそのままpractice通ったので無念です。以下ちょっと整理したもの

続きを読む

競技プログラミングのためのD言語(4/2)

21:47 |

言語というかライブラリによって意外と違うのが標準入出力の速度で、入力サイズ N の線形オーダ O(N) で解かないといけない類の問題では、注意しないとデータを読み込むだけでタイムアウトするのも日常茶飯事です。その辺の心配はないのか調べてみました（今までDでそういう問題解いたことがなかったのでした…）。以下、

• 100万未満の自然数が一行に3個、100万行、のランダムデータの総和を計算
• gcc 4.7.0 と dmd 2.059
• Core i7 2.7GHz の Windows7 で PowerShell の Measure-Command コマンドで5回測定して中間値

をとった結果です（単位は秒）。最適化ありというのは g++ -O3 と dmd -O -release -inline で、なしというのは引数なし。

なにかの優劣比較をしたいわけではないので、まったくひとかけらも厳密なベンチマークではありませんが、結論としては、まあ readln + split で問題ないのではないでしょうか、と思いました。というか、だいたいこんなオーダなのでOnline JudgeにD言語を入れる人は参考にしていただければという感じです。あと iostream が遅くてコンテストで困るという人はまずは tie(0) と sync_with_stdio(false) を (定期発言)。

// (1) C++ iostream (手抜き)
#include <iostream>
using namespace std;

int main() {
	long long total = 0;
	for(int a,b,c; cin>>a>>b>>c; )
		total += a+b+c;
	cout << total << endl;
}

// (2) C++ iostream (真面目)
#include <iostream>
using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	long long total = 0;
	for(int a,b,c; cin>>a>>b>>c; )
		total += a+b+c;
	cout << total << endl;
}

// (3) C++ scanf
#include <cstdio>
using namespace std;

int main() {
	long long total = 0;
	for(int a,b,c; scanf("%d%d%d",&a,&b,&c)==3; )
		total += a+b+c;
	printf("%lld\n", total);
}

// (4) D readln + split + to!int
import std.array;
import std.conv;
import std.stdio;

void main() {
	long total = 0;
	for(string s; (s=readln()).length; ) {
		auto ss = s.split();
		int a = ss[0].to!int();
		int b = ss[1].to!int();
		int c = ss[2].to!int();
		total += a+b+c;
	}
	writeln(total);
}

// (5) D readln + split + map!(to!int)
import std.algorithm;
import std.array;
import std.conv;
import std.stdio;

void main() {
	long total = 0;
	for(string s; (s=readln()).length; ) {
		auto ss = s.split().map!(to!int);
		total += ss[0]+ss[1]+ss[2];
	}
	writeln(total);
}

// (6) D readf
import std.array;
import std.conv;
import std.stdio;

void main() {
	long total = 0;
	for(int a,b,c; readf("%d %d %d\n",&a,&b,&c); )
		total += a+b+c;
	writeln(total);
}

// (7) D scanf
import std.c.stdio;

void main() {
	long total = 0;
	for(int a,b,c; scanf("%d%d%d\n",&a,&b,&c)==3; )
		total += a+b+c;
	printf("%lld\n", total);
}