ICPC ひとり地区大会 2013 杭州

ひとりで地区大会練習をした。（LiveArchiveで）

AC	Penalty	A	B	C	D	E	F	G	H	I	J	K
7	977	56+3	144+0	9+0	-	-	211+1	+1	176+0	68+0	233+0	-

（"-" は提出なし、"+n" は n 回誤答を提出、"m+n" は n 回誤答を提出した後に m 分の提出で AC）

本番順位表だと 6 位だった。 G が分かって書けたが WA で悲しい。

以下、問題について。

1マスにライトを高々1個しか置けないとか、回転できるライトは1個しかないとか、そういう重要なところを読み飛ばしまくったせいで 3 回も WA を出した。よくなさすぎる。

完全にやるだけなんだけど、そもそも問題を開き忘れていて開始 2 時間過ぎぐらいまで存在に気づいていなかった。さすがに本番でやる類のミスではないにせよ、ちょっとひどい。これがなければペナルティが結構減っていたはず。

やるだけ

共通部分を持たない 2 円 C1, C2 と、その 2 円の外にある 1 点 P が与えられる。P を通り、C1, C2 に外から接する円をすべて求めよ。

普通に考えても大変なことになって無理そう。問題文も不穏。

A, B, X[0] と素数 M による線形合同法で作った擬似乱数列

X[n] = (A * X[n-1] + B) % M

がある。S, K, C に対して

X[X[K] % K] % S = C

が成り立っている。A, B, M, S, K, C が与えられるので、ありうる X[0] の値を 1 つ求めよ。

A, B, M, S は 10^18 ぐらいで K は 10^5 ぐらい。

無理では。

頑張って実装するだけ。しょうもないバグを入れたのは反省。

n 頂点の重みつき無向木がある。パスの重みは通った辺の XOR sum とする。

「重みが k 番目に大きいパスの重みは何か？」というクエリに m 回答えよ。

n, m, k ぜんぶ 10^5 ぐらい。

XOR のペアを探す問題にして、探索を途中で止めた形を保持しておいて、少しずつ進めていく。今までこういうの実装したことがなかったので結構戸惑ったが、なんとか書けた。でも WA が時間内にとりきれなくてつらかった。

n 要素の数列 A がある。

「B = A[L..R] とする。B の要素のうち、自身以外のすべての B の要素と互いに素なものは何個あるか？」というクエリに q 回答えよ。

n, A[i], q ぜんぶ 10^5 ぐらい。

発想を逆転して、ある値が他全部と coprime になるようなクエリがどんな形かを考えると、 L, R の範囲がそれぞれ指定されるということがわかる。そうすればあとは難しくない。

普通のゲーム。

N x M のグリッドに P + Q 個のルーク（チェス）を置くことを考える。P 個のルークは白くて Q 個のルークは黒い。

黒いルークは他のどのルークからもとれる位置に置いてはいけない。

白いルークは 1 つまでなら他のルークからとれる位置にあってもよい。（2つ以上からとられる配置はダメ）

黒いルーク同士と白いルーク同士は区別できないとして、置き方は何通りあるか？

N, M, P, Q ともに 200 ぐらいで、200 ケース。

こういうのはいつまで経っても頭が混乱してなかなかサクッと解けない。一回迷走して変なコードを書いてしまったのが良くなかった。落ち着いて書きたい。

よくわからん。