AOJ 2021

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021&lang=jp

は?これも難しくないか?
普通にO(MN)頂点O(MN^2)辺のグラフでダイクストラすればいいんですが、これだと若干重くないか?ということで、O(N^3)解法にしました。

Aから中継点を数カ所挟んでHに行くわけですが、その間、距離M以上は移動できません。
逆にこの条件さえ満たしていれば、AからHへの最短距離をdとして、答えはmax(d, 2d-M)です。
なぜかというと、d<=Mの時は答えがdになることは言うまでもなく、d>Mのとき、d-Mだけ補給しなければなりません。よって答えの下界はd+(d-M)=2d-Mになるわけですが、これは達成できます。max(d,2d-M)はd<=Mのとき、d>Mのときで答えと一致します。
あとはワーシャルフロイドを2回やればいいです。1回目は、全頂点間で、2回目はAとHと中継点で長さがMより大きい辺を除いたグラフで行います。

しかしダイクストラより遅くてかなしぃ。

int N, M, L, K, A, H;
bool blood[110];
ll d[110][110];
ll e[110][110];

void solve() {
	while(true) {
		cin >> N >> M >> L >> K >> A >> H;
		debug(K);
		if(N == 0) break;
		memset(blood, 0, sizeof(blood));
		rep(i, 0, L) {
			int a; cin >> a;
			blood[a] = true;
		}
		blood[A] = true; blood[H] = true;
		rep(i, 0, N) {
			rep(j, 0, N) {
				d[i][j] = inf;
				e[i][j] = inf;
			}
		}
		while(K--) {
			int a, b; ll c;
			cin >> a >> b >> c;
			MIN(d[a][b], c);
			MIN(d[b][a], c);
		}
		rep(k, 0, N) {
			rep(i, 0, N) {
				rep(j, 0, N) {
					MIN(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
		rep(i, 0, N) {
			rep(j, 0, N) {
				if(blood[i] && blood[j] && d[i][j] <= M) {
					e[i][j] = d[i][j];
				}
			}
		}
		rep(k, 0, N) {
			rep(i, 0, N) {
				rep(j, 0, N) {
					MIN(e[i][j], e[i][k] + e[k][j]);
				}
			}
		}
		if(e[A][H] == inf) {
			cout << "Help!\n";
		}
		else {
			cout << max(2 * e[A][H] - M, e[A][H]) << "\n";
		}
	}
}

AOJ 2011

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011&lang=jp

は?むずくないか?
DPできないと思ったので、貪欲でやりました。
うしろから見ます。k日間でできるとします。k日目スケジュールが入っている人の集合をSとします。k-1日目でSに全部の地図が集まれば良いです。k-1日目にスケジュールが入っている人の集合をUとします。もし、Sの要素vの中でUに含まれるものがあったら、Uに含まれる人はvに地図を全て渡せばよいです。なのでS=S∪Uとupdateしてk-2...1日目まで再帰的に計算します。Sに全ての人が含まれていれば成功です。

Codeforces Round #503 (by SIS, Div. 1)

https://codeforces.com/contest/1019

Aで無限に時間を使ってしまい、絶望的だったので撤退…いやでも今後のためにも提出したほうがよかったかなぁ…

A
普通に勝たせる人に何票入れるかで全探索すれば良いんですが、いろいろこんがらがってしまいだめでした…
B
真面目に読んでないんですけど、どうせ二分探索です。
C
1点について見てから、適当に頂点を削除して、再帰的に構成するっていうのを本番も思いついたんですが、形にはできず…
結局2-SATに流れてしまいました…でも2-SATでもO(M)個の値のorが必要だったのでできなさそうです。
あとn=10^6の時は本当に単純じゃないとTLEするので注意です。今回も対して複雑ではないけど1824ms/2000msとかだったので。

できることを素早くできるようになって、できないことを判断できるようになったらだいぶ良くなりそう。

AOJ2383: Rabbit Game Playing

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2383

350なのに全然解けない…と思ったら誤読で悲しかったです。
でも誤読した問題も少しおもしろいので紹介したいと思います。

今までプレイした最高難易度と同じもしくは簡単な問題を解くことがT回以下だった場合の数を求めよ。
ex.
1 3 2と解いた場合は1回、1 2 3と解いた場合は0回、3 2 1や3 1 2と解いた場合は2回です。

うしろから見てdpすればO(N^2)です。

下は元の問題のACコードです。

int N, M;
int A[MAX_N];
int S[MAX_N];

void solve() {
	cin >> N >> M;
	rep(i, 0, N) {
		int a; cin >> a;
		A[a]++; S[a]++;
	}
	C_init(N + 10);
	rep(i, 1, 100000 + 1) {
		S[i] += S[i - 1];
	}
	ll res = 1;
	rep(i, 1, 100000 + 1) {
		if(A[i] != 0) {
			MUL(res, C(S[i - 1] - S[max(i - M - 1, 0)] + A[i], A[i]) * fac[A[i]] % mod);
		}
	}
	cout << res << "\n";
}

Codeforces Round #469 (Div. 1)

https://codeforces.com/contest/949

ABしか解けないよぉ助けてくれ

A
最大のzebraを取っていけばいいことはわかりますが、実装にてこずりました。こういうのはsetって一番言われてる。
B
再帰的に求めていけばいいです。
C
最近有向グラフの問題といてなくていろいろこんがらがった…SCCするだけなんですが、N=2のコーナーケースに引っかかってしまった…
D
区間に値を割り振っていく問題になって、greedyでできます。O(Nlog^2 N)とかですが大丈夫です。multisetとすべきところをsetとしてしまいWA...
解説の方は人同士が交わらないことを利用してO(N)でやってるんですがこれも思いつくべきでした。

べつにABCDまではそんな難しくないですけど、やっぱりコンテスト中に解くとなるとあせりとかもあるし難しいですね。脊髄を鍛えたい。
問題文を読解するのに時間がかかってしまったのも問題ですね。

Codeforces Round #485 (Div. 1)

https://codeforces.com/contest/986

AB397位
A
bfsします。
B
3nと7n+1で偶奇違うのに気づくのにすごい時間かかってしまった…。
C
こういうグラフの問題は初手をミスるとなんにもできなくなりますね…。
補助グラフを使ってうまくまとめる感じです。

https://codeforces.com/problemset/problem/1012/B
これは今回の問題とは全く関係ないですが、グラフにそもそもきづけなくて解けなかったやつなのであげときます。

D
2*2*3*3*3...みたいな形をしていることがわかればあとは大小比較をすればいいです。FFTでやれば厳密にできるらしいです。

Educational Codeforces Round 48

http://codeforces.com/contest/1016

このコンテストで全完できるようになったらめちゃくちゃ気持ちよさそうですね…
A
読んでないです。
B
O(NQ)でゆるーくやりましょう。
C
めんどくさい…横移動するとあとはコにしか動けません。
D
条件を連立方程式にして、行列を変形していくと、YES<=>aとbのxorが0になります。構成は1行目と1列目を適当に決めればいいです。
E
頑張って条件式を立てると、結局r-lに依存しないので線形性でまとめてO(NlogN)だと思うんですけどなんで通らないんですか。
F
trivialじゃない木が直線+len1の枝が生えてるみたいな感じです。実装絶対めんどくさい。
G
LCMの条件からvとaiはLCMの約数なんですが、たかだか2000コです。なのでO(2000*2*10^5)で通ると思います。

なんかいろいろ書いてるんですけど実際本番で2完しかしてないのやばい。