こ れ は な い

今年の情報オリンピック本選の問題が公開されてたので見てみたのです。
これはよいリフレッシュ。
http://www.ioi-jp.org/
http://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/index.html
http://www.ioi-jp.org/joi/2008/2009-medalists.html
しかしまあ満点で金賞が３人とはえらいことですなあ。
昔から願ってたことだし喜ぶべきことなんだろうけど同時に何かが遠い所に行ってしまう感覚があるのもまた確か。

やはり３（あみだくじ）あたりからぱっと見当がつかなくなって怖くなってきますね。４．散歩で詰まったのでがんばった。４問完答で銀メダルなんだよね。毎年こっそり過去の自分の正当性維持のためにヒヤヒヤしながらがんばっているのであります。

※制限時間１秒

real 1.061s
user 0.919s

うーん？温情採点がくるかもしれんけどこれでこんなにギリギリ・・・？
なんかおかしくないか・・・？
入力ファイルをポータブル外付けHDD→内蔵HDDにコピー

real 0.047s
user 0.000s

ねーよ
なんかものすごい甲高い奇声をあげていました。
こちとらノーパソでHDD80GBなんだよ！こっちにはソフトウェア入れるだけにしてデータはみんな外付けにしてんだよ！競技用にレンタルしたノーパソとは訳が違うんだよ！！訳のわからない数字がそれこそ10^6個オーダーでただひたすら書かれているテキストファイルを誰が展開するか！ばーか！ばーか！

もうなんかいろいろと開放的な気分になってきたので問題の４．散歩の解答を投下。説明はなし。つまり問題の解答・解説としての機能はほぼ果たせない。アルゴリズムの問題の解説ってのはソースコードも疑似ソースコードもほとんどの場合あまり有効じゃないと思うね。自然言語の方が説明側も柔軟な表現が可能で聞く側もわかりやすい。

#include <cstdio>
using namespace std;

int main(){
	int h, w, n;
	static int map[1000][1000];
	static int count[1000][1000];
	scanf("%d%d%d", &h, &w, &n);
	for(int y=0; y<h; y++){
		for(int x=0; x<w; x++){
			scanf("%d", &map[x][y]);
		}
	}

	n--;
	count[0][0] = n;
	for(int k=0; k<w+h-2; k++){
		for(int x=0; x<=k; x++){
			int y = k - x;
			if(x >= w || y >= h)
				continue;
			if(y+1 < h){
				count[x][y+1] += count[x][y] / 2;
				count[x][y+1] += map[x][y]==0 && count[x][y]%2==1 ? 1 : 0;
			}
			if(x+1 < w){
				count[x+1][y] += count[x][y] / 2;
				count[x+1][y] += map[x][y]==1 && count[x][y]%2==1 ? 1 : 0;
			}
		}
	}
	for(int x=0; x<w; x++){
		for(int y=0; y<h; y++){
			map[x][y] ^= count[x][y] & 0x1;
		}
	}

	int tx = 0;
	int ty = 0;
	while(tx < w && ty < h){
		if(map[tx][ty] == 0){
			ty++;
		}
		else{
			tx++;
		}
	}
	printf("%d %d\n", ty+1, tx+1);
	return 0;
}

ヒント：n-1回通った後のパネルの状態を素早く求め、その後(1,1)からパネルに沿って進もう。