ABの二完で終了。
復活してからのARCでは失敗が少なかったのに。悲しい。
A - Simple Math 2
かなり長いこと分からなかったのですが、
$10^N=p*M+r$
とおき、さらに、
$p=q*M+ANS$
とおいて、下式を上式に代入すると考えると、$M^2$での余りを考えれば良いと気付けました。
B - Reversible Cards
既出らしいですが、気付けませんでした。
当時は解けていなかったので、今回は解けて良かった。
C - Too Heavy
ツイートか何かで「重い荷物の順番に交換すれば良い」というほぼ答え同然の情報を得ていても、30分程度実装にかかってしまった。
どういう問題なのか、情報を整理するのか難しいと思う。
頭の整理のため、
・B：荷物の番号→荷物の重さ
・P：人物の番号→持っている荷物の番号
（及び、・Pの逆関数：荷物の番号→人物の番号）
と、それぞれがどういう関数かメモしたら多少分かりやすくなったが、それでも苦戦した。
D - Orientation
iとjを結ぶ辺で、C[i]とC[j]が異なるなら、Cが大きい方から小さい方へ結べばよい。
問題は、同じときにどうするか、だが、公式解説にある通り、よく考えるとDFSするだけで良い！ となる。
確かに、よくDFSの性質を考えてみればそうなりそうで、証明はDFS木などを使えばできる。
ただ、それが自然と感じられるためには、DFS木、lowlink、橋といったあたりに親しんでいることが必要そう。勉強不足でした。
今調べた中では、hosさんのpdfが一番分かりやすかった。AOJにも入っている内容なので、ちゃんとやっておかねば。
E - Simple Math 3
snukeさんの解説動画を見てAC。
floor sumを使うと分かっても戸惑ってしまった。けど、その知識があるなら解けなきゃダメですね。図を描いて、順を追って考えればfloor sumが出てくるという問題なので。
F - Do you like query problems?
snukeさんの解説動画を二回見てAC。
一回解説動画を見た時点だとよく分からなかったのだけれど、もう一回見たら意外と単純だと分かりコードにできました。
解説動画を理解する上でのポイントは、
・N=1のとき、「k回目のクエリでsumを取るときに加算される値」が$C^k*$（係数）の和
みたいに表せるので、kを1～Qで動かした和が等比数列の和の公式で求められ、大体O（１）なこと。（繰り返し二乗法を使うので本当はO（１）ではありませんが）
・N=1の場合で求めたA, X, Bが、Nが一般の場合でも求められること
といった辺りだと思います。
何を教訓とすべきかは難しいです。特に、一回解説動画を見た後もできなかったのは、何かが思いつかなかったのではなく、複雑な状況を理解し式に落とす力がなかった、という感じなので。
こういう、複雑な状況を整理する力はどうすれば身に着くんでしょう。マラソンをやると効果があったりしないかな……。
0 件のコメント:
コメントを投稿