情報オリンピック2009-2010 本選１旅人

そうかそんな時期かということで。最近こっち系のは全然やってなかったので高校生用のこれに甘えようとしたら当身から即死しました。というか１と３の２問で合格、２ができたのは(多分メダルの)３人だけという。去年と同じだと公式の解説upがめちゃくちゃ遅くなりそう…。マイコン班wikiに転載してもいいのよ？
問題とデータいろいろ
http://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/index.html
制限時間は５問で４時間。実行時間制限は全問１秒。メモリ制限は全問64MBでした。
言語の壁みたいなもので読みにくくなると嫌なのでCで書きますが、変数宣言を一番上に書くのが嫌です。いや、gcc -Wall -O2 -lmで通ればいいんだから別にいいんじゃないかっていう…。

問題１
1..nのn個の宿場町があり、n-1個の配列sで間の距離がそれぞれ与えられる。m個の配列aが与えられ、宿場町1からスタートし、aに従って移動する。移動距離の合計(mod 100000)を求めよ。
n <= 100000, m <= 100000, 1 <= s[k] <= 100

解法の解法
こういうのが一番欲しいと思うから書く。問題PDFの「入出力の例に対応する図」をガン見。矢印の左端があると線分の数が１増え、右端で１減ることがポイント。右に動く(a[k] > 0)か左に動く(a[k] < 0)かで現在地と移動先が右端か左端かが変わることに注意する。

count[k]に、左から見ていったときにk番目の宿場町から何本矢印が増えるかを入れる。減るときは負の数。最後にsum = 0;から始めてcount[k]を足していくと宿場町k〜k+1の道路を通った回数が得られる。道路の長さ×回数を足していけば完成です。回数は高々m = 10^5、距離は高々s = 10^2なので符号付き32bitがだいたい20億までなのと合わせてこの操作１回あたりでmod 10^5をとっていれば大丈夫であることを慎重に確認して終了。変なところでミスると非常にだるい。

#include <stdio.h>

int main() {
	int n, m;
	static int dist[99999];

	static int count[100000];
	int pos = 0, sum = 0, ans = 0;
	int i, k;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n - 1; i++) {
		scanf("%d", &dist[i]);
	}
	for (i = 0; i < m; i++) {
		int a;
		scanf("%d", &a);
		if (a > 0) {
			count[pos]++;
			count[pos + a]--;
		} else {
			count[pos]--;
			count[pos + a]++;
		}
		pos += a;
	}
	for (i = 0; i < n - 1; i++) {
		sum += count[i];
		ans += dist[i] * sum;
		ans %= 100000;
	}
	printf("%d\n", ans);

	return 0;
}

ちなみに風邪＋睡魔＋ブランクの中やったところ、１時間ほどかかりました(爆笑)。衰えたな、ユダ…。