コンテストへのリンク
B. Bogosort
大きい順（降順）にソートすればOK。
・まず極端な場合を考えてみる
という意味でもソート状態を考えてみるのが良い。
また、立式して考えるのも良い。
$A_i-i=A_j=j$でi<jのとき、必ず$A_i<A_j$なので、そうならないようにする、という方針でも思いつけると思う。
C. Adding Powers
$k\geq 2$のとき、$k^n$は$k^1, k^2, ... , k^{n-1}$の和より大きい、ということを利用する問題。
これが成り立つので、kのベキ達の和である数を作るためには、できるだけ大きいベキを使わなくてはいけない。
D. Count the Arrays
・Combi(m, n-1) : m個の数から、互いに異なるn-1個を選ぶ。（一組の数字が一致しているので、互いに異なるのはn-1個）
・n-2 : 一致する数を選ぶ。増加列と減少列の間には最大の数が来るしかないので、それを除いたn-2個から選ぶ。
・$2^{n-3} : 最大値と、一致する数を除いた残りn-3個の数を増加列か、減少列かのいずれかに割り振る。
これで題意の配列が定まるので、この積が答え。
E. Array Shrinking
コンテスト中に区間DPだと思いつつも解けなかった。
DP[i][j]で、区間[i, j]が一つの数字に縮約できたときの値、とすれば良い。
この定義は今見ると自然に見えるけど、確かに、「縮約したときの最小の長さ」をDPの値に持ちたいと思ってしまうと、ハマってしまうか……。
そのDPテーブルを利用して、長さの最小値も求められる。（あるいは、けんちょんさんの記事のように、同時に求めることもできる）
また、かっつさんの記事にありますが、もっと計算量は速くなるらしいです。
F. Attack on Red Kingdom
一応、自力AC。最近Grundy数を復習したのを覚えていたから解けただけで、コンテスト時に解くことは無理だったと思う。
こういうタイプのゲームはGrundy数を考えるしかない。
x, y, zが小さいので、それぞれについてGrundy数を前計算しておく。
問題は、$a_i$が大きいことだけど……。
まあ、Grundy数はどこからか周期的になっているはずで、大きくても2520（1~10の最大公約数）周期にはなっているだろう、と思い、$a_i\geq 5400$のとき、$a_i =a_i$ %2520+2520$としたらACした。
公式解説を見たら、周期もちゃんと調べてますね。
G. Autocompletion
アルメリアさんの解説記事、けんちょんさんの解説記事があったので解説ACしました。アルメリアさんの記事はかなり詳しく書いてあり、ありがたかった。
Trie木について理解していなかったこともあって、問題文の読解から苦労してしまったのですが、やること自体はそこまで難しくないですね。
ただ、「ある点から子孫の点へワープするときのコストの減少幅」がどの子孫へ行くときも一定というのは、意外な気がしてしまいました。これが直感的に正しいと思えれば解くのは難しくなさそう。
Trie木の勉強にもなったので良かったです。これを機に、Trie木を使う問題を一つくらい解くべきかなぁ……。
0 件のコメント:
コメントを投稿