AtCoder Grand Contest 017
Updated:
【AGC017】
— AtCoder (@atcoder) 2017年7月9日
コンテストは終了いたしました。ご参加ありがとうございました。
解説PDF：https://t.co/oTzYbATfNX
解説放送：https://t.co/181eB0eVWM
Source codes
Solutions
A - Biscuits
- $A_1, \dots, A_N$ が全て偶数の時、 $P=0$ なら答えは $2^N$ 、$P=1$ なら答えは $0$ 。
- それ以外の時、答えは $2^{N-1}$ 。
B - Moderate Differences
AGC017
— Kazune Takahashi (@kazunetakahashi) 2017年7月9日
A: 偶数と奇数の個数を数えて計算
B: 以下を判別。 pic.twitter.com/56YDmjc1Hk
B は O(N) で間に合うか心配だったので不等式解いた
— Kazune Takahashi (@kazunetakahashi) 2017年7月9日
C - Snuke and Spells
全部 $1$ 引いておく。 $0 \leq i \leq N-1$ に対し、 \[ C_i = \sharp \{ 0 \leq j \leq N-1 \mid A_j = i \} \] とする。 区間 $[0, N-1]$ を $[\max(0, i-C_i+1), i]$ たちで 被覆できるかという問題に帰着する。被覆されていない区間の個数が 変更が必要な元の個数である。 \[ S_j = \sharp \{ 0 \leq i \leq N-1 \mid j \in [\max(0, i-C_i+1), i] \} \] として、各クエリで $C_i, S_j$ と答えを更新する。
ポイント
実際は数字が変更されていないクエリ は、何も処理せず同じ答えを出力するようにしておくのが無難である。変更前と変更後でミスが出やすい。
処理が可能かどうかを 区間の被覆 とみるのが解法のポイント。うーん、応用は効くのかしら。
D - Game on Tree
まず『プログラミングコンテストチャレンジブック』で Grundy 数の確認をする。 状態 $S$ の Grundy 数 $G(S)$ は、 \[ G(S) = \min \{ n \in \mathbb{N} \mid (\forall S^\prime)( S \mapsto S^\prime \Longrightarrow G(S^\prime) \neq n ) \} \] と定義される。ここで $S^\prime$ は状態であり、 $S \mapsto S^\prime$ は $S$ から $S^\prime$ へ $1$ 手で遷移できるということを意味するものとする。
今回の場合、根から複数個生えている枝は、全て独立した別の根に突き刺さっているものとして、あとで xor をとればいい。そこで問題は、根から $1$ 個しか生えていない場合であるが、 $T$ の根に枝を $1$ 本生やして根を取り替えた木を $T^\prime$ とすると、 $G(T^\prime) = G(T) + 1$ が成立する。定義に基づいて証明できる。あとは再帰するだけ。
ポイント
Grundy 数だと気づくためのポイントは、 「全く同じものが $2$ つあったときに、相手と同じように行動していけば後手が勝てる」 という状況であるかどうかだと思う。今回の場合、根に全く同じ木が枝としてついていれば「同じように行動していけば…」の状況になっている。
E - Jigsaw
ピースが組み合わさるときに同じ頂点を共有するように、ピースを有向辺とみなす。 入力数と出力数も計算しておく。具体的には以下の通り。
void add_edge(int i) {
int from, to;
if (C[i] == 0) {
from = A[i];
} else {
from = -C[i];
}
if (D[i] == 0) {
to = -B[i];
} else {
to = D[i];
}
V[from + M].push_back(to + M);
output[from + M]++;
input[to + M]++;
}
ピース同士が「隣に」置けるのは、ぴったり噛み合う時か、左に負のピースかつ右に正のピースが来た時。後者は別のセグメントがたまたま隣にきたと解釈できる。これをグラフに言い換えると、セグメントとは正の頂点から負の頂点へのパスである。グラフがこのパスの組み合わせとして分解できることが問題の答えが YES であるための必要十分条件である。
このためには、基本的に入力数と出力数を見てやればよろしい。正の頂点は入力数 $\leq$ 出力数、負の頂点はその逆であればよろしい。これがみたされていないのは以下ではもう弾いているものとする。
閉路が問題になる可能性がある。閉路にヒゲがくっついているような奴は閉路をぐるっと回ってやれば全部大丈夫だが、連結成分が閉路だけでできている場合はこれができない。二重ループや数珠のような形も不可能である。だから 連結成分全体がループだけでできていないか を判定することになるが、これは全ての頂点で入力数 $=$ 出力数であることと同値である。
ポイント
自力では解けないと思う。閉路といえばトポロジカルソートで検出はできるのだが、今回は閉路に様々な形があり得る。自己辺もあるくらいだ。 入力数と出力数 で捉えるのが鍵である。
F - Zigzag
解説読んでも聞いてもわからなかった。放棄します。
Others
書くのにかかった時間
A - sample: 4, tle: 2.000, time: 08:47, from_submit: 368:08
B - sample: 4, tle: 2.000, time: 48:16, from_submit: 319:51
C - sample: 3, tle: 2.000, time: 194:31, from_submit: 125:21
D - sample: 4, tle: 2.000, time: 66:07, from_submit: 59:14
E - sample: 3, tle: 2.000, time: 59:14, from_submit: 00:00
F - sample: 4, tle: 4.000, time: 00:00