2020 TCO ALGORITHM ROUND 1B 解説

公式解説

Easy: ELLYSCANDIES

この問題は実は、最後に選択した方が勝つ。
間違っても、制約がN=20だし、ゲーム問題だから、bitDPでminimax法で…なんてやってはいけない。
いつも順位表をだしながら問題を解いてるのだが、上位層が1分もたたずに解いているのを見て、
貪欲だろうなぁと思いながらbitDPをせこせこ書いていた。

端的に言うと、Nが偶数なら後手（Kris）の勝ち、奇数なら先手（Elly）の勝ちである。
なぜか。
例えば、5ターンまでにp1, p2, p3, p4点取っていたとする。
すると、5ターン目では、p1+p2+p3+p4+x点を取ることができる。
つまり、全体累計以上の点数を一気に取得するということ。
なので、最後に取った人の勝ちになる。

Med: ELLYSWHATDIDYOUGET

(x,y,z)の組は50³通りだし、1～Nも最大100通りなので、全部試しても間に合う。
12500000通りで10⁷通りくらいなので、オーダーではギリギリくらい。
今回は簡単な計算なので、10⁸オーダーくらいでも間に合いそう。

Hard: ELLYSDIFFERENTPRIMES

公式解説

N, N-1, N+1, N-2, N+2, N-3, N+3, N-4, N+4, ..のようにN周辺で答えの候補を探していく。
以下の2関数を作って判定する。
isDifferent(x) := 数xの各位の数がすべて異なるか
isPrime(x) := 数xが素数かどうか
isDifferentは文字列にして判定しても間に合いそうだし、数のままやった方が軽い。
isPrimeは、O(sqrt(x))で素数判定するやり方があるので、それを使う。
2～sqrt(x)で割れるものがなければ素数と判定するやり方。
色々実験すると、10⁶以内くらいには全部ありそうな感じがする。

自分の解説

5×10⁷以上で、条件を満たす最小の数は50123467である。
よって、答えの候補は50123467以下で考えればいい。
各位の数がすべて異なる数をdfsを使って50123467以下で全列挙すると、1.4×10⁶個くらいになる。
この列挙はそんなに重くない。
この中で素数であるものを判定して、絞ると、8*10⁴個くらいになる。
これをソートして、最も近いものをこたえる。
1.4×10⁶個くらいを素数判定する部分が一番重いが、ラウンドロビン素数判定でループ10回くらいにすると、TLEを避けつつ精度を保てる。
他の人の解法では、50123467でエラトステネスしてる解法もあった。
（やったらむっちゃ遅かったけど）