CADDi 2018 C, D 考察

CADDi 2018 C - Product and GCD

解説 AC 。

考えたこと。 N, P <= 10^12 なので前から順に求めるのは難しそうだ。かけて P になる数だし 10^12 という制約からおそらく素因数分解する (O(√P)) 。 gcd(a_i, a_{i+1}) を最大化するには……。わからん……。

解説によると gcd(a_1, ...) を g とすると P は g^N の倍数になる。 a_i はどれも g の倍数で N 個かけているのだから確かにそうだ。 P を素因数分解したときの素因数と g を素因数分解した素因数は一致するはず。 P を素因数分解したときの素因数のかたにのっている数字を N で割って切り捨てた数のとき g が最大になる。

わかるようでわからん。自分で見つけられるだろうか。そしてこれが茶色 diff なのか……。嘘でしょ……。

https://atcoder.jp/contests/caddi2018/submissions/15718970

CADDi 2018 D - Harlequin

いくつか例を書いて仮説を試したら AC した。

• 1 のとき first になる。
• 2 のとき second になる。
• 3 のときは first になる。
• ここまでで 1 種類のとき奇数なら first 偶数なら second になるとわかった。
• 1 1 のとき first になる (すべて取って勝てる) 。
• 2 1 のとき first になる (1 を取れば相手を 1 種類で偶数の状態にできるので勝てる) 。
• 2 2 のとき second になる (1 を取ると 2 1 で相手番になり負ける。 1 1 を取ると 1 1 で相手番になり負ける) 。
• 3 1 のとき first になる (1 を取ると 2 1 で相手番になり負ける or 3 で相手番になり負ける。 1 1 を取ると 2 で相手番になり勝てる。) 。
• 3 2 のとき first になる (1 を取ると 2 2 で相手番になり勝てる) 。
• 1 1 1 のとき first になる (すべて取って勝てる) 。
• 2 1 1 のとき first になる (1 1 をとって 2 で相手番にすれば勝てる) 。
• 2 2 1 のとき first になる (1 をとって 2 2 で相手番にすれば勝てる) 。
• 2 2 2 のとき second になる (いろいろ試したが勝てない) 。
• ここまでで全部が偶数のときに手番を持つと負けると推測した (逆に 1 種類でも奇数のものがあればそれらをすべて取って相手番にすれば勝てる) 。

答えとしては前から順に走査して奇数がひとつあれば first ひとつもなければ second 。 O(N) N <= 10^5 。

https://atcoder.jp/contests/caddi2018/submissions/15725585

リングフィットアドベンチャー 50 日目。

いろいろやりたいことがあるはずなんだけどどうも調子が出ない。