最終更新: 2021-05-04T20:49+0900
先週末の ABC。例によってお風呂で考えるも頭が爆発して無理だと思われた F 問題が、なぜか今日取りかかってみれば解けたので日記にする。
すごく難しくて、じっくり 10 分の時間をかけた。
Aoki と Takahashi の文字列を２回書いているところに余裕のなさが見える。間違えるくらいなら全パターンを網羅して並べればいいんですよ(言っていることが違う>20201101p01.03)。
A 問題より簡単だった。条件を満たすものが１つでもあればいい。Array#any? メソッドの出番です。
ところで空配列に関して、[].all? は true を返し、[].any? は false を返す。この違いによってメソッドの選択が制限されることがあるかなと一応警戒するんだけど、特にそういう違いは生まれないみたい。むしろそうならないようにデフォルト値が選ばれている。罠があるとしたらそこではなく、穴に落ちるときは all? を選んでも any? を選んでも落ちる。
制約が K に関して全探索しろと言っている。
Ruby で最も速い提出(492 ms)より倍以上遅いんだけど、どういうことなんでしょうね。
本当は今日は F 問題をやるつもりはなくて、この C 問題を速くするつもりで取りかかったのだけど、優先順位をつけた深さ優先探索でやろうとしてうまくいく見通しが立たなかったのだった。
45 分考えた。等差数列の和の公式に２種類あることはこのときに確認済みなので(20201101p01.02.01)、今回は使いやすい方を選ぶことができた。
珍しく解答の中にコメントがあるのは、書いておかないと脳みそからあふれて何度でも最初から考え直しになるからです。紙と鉛筆を用意すべきなんだよなあ。
本番中は残り時間が 30 分しかなかったので問題文が短い F 問題に先に取りかかっていた。同じように考えたかどうかはわからないが、E 問題より F 問題の方が多くの人に解かれていたようだ。自分はどちらも解けなかった。
制約が３重ループを許すと言っている。
解答の後半はもう３回目になるあの形。実行速度にハンデを背負った Ruby でのタイムの詰め方は、このときに研究し尽くした>E 問題 Traveling Salesman among Aerial Cities。
惜しい。とても惜しい。時間制限が２秒なのだけど、実行を打ち切られたときは 22xx ms というタイムになる。32 ms 詰めれば AC になるぞ。
ハッシュ表を使っていたところで配列を使ったら余裕の AC。
必然性があってハッシュテーブルを選んでいたわけではなくて、Hash のデフォルトプロックありきでスクリプトを構成していたから、使っていた。TLE は邪道の報い。
実は唯一の TLE は最も重いケースではなかった。この提出では TLE だった 21_large.txt のタイムが 135 ms だ。
前半部分で選ばれた魔法石がどうがんばっても連結できないとわかれば、後半の３重ループはスキップできる。そういうこと。
前半部分で距離の確定を双方向からやらずに片方向で済ませてみたら、平均的には速くなったけど、一番遅いケースでは 25 ms しか違わなかった。
Integer#times を while ループにするだけで 200 ms 縮んでやんの。そんなに違うの？ times はイテレータの中では速い方だと思ったけど。
転倒数って固有名詞なのかな。公開された PAST の過去問をやったときに見た>20201111p01。K 問題。それが解いてあった(提出 #18029328)からといって、何かが役に立ったということはない。残念。
最初に、k を増やして数列の初項を最後尾に送り込んだときに、転倒数がどのように増減するかがわかった。わかったからわかったとしかいいようがない。こねくっていたら、転倒数の増減が簡単な計算で求まることがわかった。
それから、転倒数の初期値の求め方を考えた。BIT で殴るのではない、頭のいい方法があるのではないかと考えたが、思いつかなかった。
BIT です。Ruby や Python で速い提出も同じだったので、転倒数はこう求めるのだ！ という頭のいい方法はないのかも。
実は A 数列をスキャンして作成していた配列 I は不要だった。
BIT を使って転倒数を求める手順も、考え方次第でひと通りではないということ。ソート列を必要とする方法よりは必要ない方法を、BIT へのお伺い(対数時間)が２回になる方法よりは１回で済む方法を選びたい。脳みそはタダだけど計算資源は有限。