ここで、1≤Pi≤8 が制約として保証されます」がどう活用できるのか。最初は８×８の 64 通りに qi+X を分類して答えを求めておけばいいかと思った。でも足りなかった。１から８までの LCM である 840 通りであれば足りた。だけど 840×N≦8400万は Ruby にはつらい数字。D 問題に続いて E 問題まで答えは出せても TLE というのは残念すぎるので、先日の精進(20230831)にならって C++ で提出したら 624 ms で AC だった。制限時間は３秒。Ruby でも２秒を切れるみたいだけど、どんな考察が求められているのかまだわからない。■F 問題「Fighter Takahashi」。薬を飲む順番を総当たりして許される制約。敵はポーションのまわりに集約できる。ポーションは直列と並列に並べられる。あとは効率良く総当たりしたいけど、うまく書けなかった。DFS でやるんかな。■■■F 問題。すでに飲んだ薬の集合をキーとして、倒せる敵をすべて倒したときの強さの最大値を記録したものを状態とする。次に飲む薬を選び、倒せる敵をすべて倒し、記録する。これでいけると思う。DFS だと飲んだ薬の集合ではなく薬を飲んだ順番を区別してしまうので、計算量が危険？ 10 の階乗はだいたい 370 万やからいけるやろって思ってたんだけど、案外遷移に時間がかかる？ つまり、倒せる敵を倒しつくすのに(※薬の倍率が１以上なので薬を飲む前に倒せる敵を倒さない選択肢はありません)。プライオリティキューを使って、敵の数×log(敵の数)＜5000。あっ、これはいけない。状態数を 1<<(薬の数) (1024 以下) に抑えてやっとなのだな。■ところで、Ruby ですでに AC になっている提出 #45433698 を答え合わせに使ってデバッグをしていたのだけど、こういう No ケース (４つの頂点が１列に並んでいて、１の直接の子が強さ９の敵) に Yes が返ってきて困ってしまった。答えが２択だとこういうこともあるかな。こちらは大丈夫みたい>#45434962 (require があって実行がやや面倒)。■提出 #45461169 (AC / 1755 Byte / 94 ms)。通った！ こんなに不安だった提出はそうそうない。Octopus (20230902) とか？ 提出をためらっているあいだに変数にコメントをつけたりなんかして。しかも２桁 ms なのが嬉しい。1.7 KB も文字を打った甲斐がある。ちなみにプライオリティキューは使ってないよ。敵は木構造を持って整列しているので線形時間のマージ操作を書いた。敵を倒すときも線形時間で走査する。これは５問目の橙 diff AC。ABC の高難度評価は当てにならないらしいけど、相対的に十分難しいのはたしか。