ここで、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 の高難度評価は当てにならないらしいけど、相対的に十分難しいのはたしか。
X.zip(L).map{|x,l| x-l }.min が十分。Ruby だから関係ないんだけど、制約が 61 ビット使うといっているので 10 倍 100 倍してテキトーに小さい数を初期値にすることをためらってしまった。それが WA の理由のひとつ。もうひとつが等距離にあるが右にあって近づいてくるお宝と左にあって遠ざかっていくお宝の扱い。近づいてくる方を短い触手に割り当てる方がお宝がつかめる可能性を高める。いやいやいやそんなんわかりませんて。ランダム入力を何十回試してもそれによる不一致は出てこないんだよ。まあ、無限ループなのでいずれ見つかるんだけど。■今日の日記にここまででタコの腕とタコの触手が出現しているけど、問題文ではタコの足になっている。実際のところタコのあれはなんなんだろう。「タコの足の本数は何本？タコの足の数はなぜ８本なの？腕が再生して９６本！ | BIJOH [ビジョー]」を読むと腕と足は間違いではないが触手には言及がない。触手について「無脊椎動物の体の前端や口の周辺にある糸状またはひも状の突起。先端に多くの感覚細胞が分布し、触覚や捕食の働きをする」と明鏡国語辞典に書いてあるのを読めば当てはまるような気がするが、違うと言われれば糸でもひもでもないからかなあとも思う。でもそんくらいしか違わないよね。ナチュラルに触手ってワードが出てくると、すわエロアニメによる刷り込みかという警戒心が働くのだけど、別に不自然な言葉選びではなかったのではないか。でもそれをここにこうして書くのはダメだと思う。
while b*b<=a; if a%b==0; c = a/b end b+=1 end なら AC で、while b<=c; if a==b*c; end c = a/b+=1 end なら TLE。AC の方では足し算１、掛け算１、剰余演算１が毎回で、約数が見つかったときだけ割り算が１。TLE の方は足し算１、掛け算１、割り算１を毎回やっている。剰余と割り算のコストが同程度なら剰余を求めないで済んでる分得かなと思うんだけど、そういう結果ではない。違うんだ？ ループ回数は同じだと思うし、どこで差がついてるのか本当にわからない。■３桁 ms の２つの提出(#20120433, #20414187)を読んだ。約数列挙に工夫があった。最初に素数を列挙している。たしかに１ずつ加算して割り切れるか確かめるより、素数について指数を調べる方が効率が良さそう。<< をおそらくヒアドキュメントの開始と勘違いしているせいで、lb メソッドと BIT クラスが折りたたみできなくなっている。直前に数値(1)があることは認識できてるんだから、ビットシフトと解釈するのが自然だと思うんだけどな。数値と文字列をそのまま並べるような文法はないのだから。■インスタンス変数 @a を ace_variable ace_instance とクラス分けしているあたり、完璧ではないけど Ruby のことを知ってそうな雰囲気はある。■レイヤー分けの弱点がこういうところに現れたのだろうか。「AtCoder の新エディタに使われている Ace、多バイト文字の扱いがたまに怪しいので、 「※」などの全角記号を使うとカーソルの位置がズレる （※は「なでしこ」の行コメントの1つ、「プロデル」のプリプロセッサとして使われている） https://t.co/YwDlWqNNjf」。ひらがなとか漢字を使ったくらいでは問題ないので、あまり気にすることはないかな。それを確かめるためにさっきリンクした(日本語変数を使っている)提出をいろいろ調べていた。■もう昨日だけどこんなんがあったらしい。「新エディタテストコンテス」。A 問題難しくない？ 前回の ABC-G に似た雰囲気を感じる。"月 日" という文字列の配列を全部生成してから真ん中を選んだんだけど、そこはさ、単に通年での day-of-year を数えておいて、文字列を生成するかわりに適切なタイミングで答えを出力すれば良かったじゃない。■C 問題「Flavors」。フレイバーごとにおいしさを記録してから異種組み合わせと同種組み合わせを考えた。ツイッターを見てると最大のおいしさが必ず採用されることに着目した解法が目立つ。そのアイスを２回食べてしまうミスにだけ注意すれば配列１本で処理できるのが魅力的な解法だと思う。ミスへの対処法は、必ず選ぶ１つを配列の先頭もしくは末尾の要素とスワップして、先頭もしくは末尾を探索範囲から外すのがいいかな。■D 問題「Magical Cookies」。最終的に E 問題の３分の１くらいしか正解者がいないいわくありげな問題。下手をするとすぐ TLE になるみたい？ 自分も 35 分と、E 問題より時間をかけて慎重にやっている。TLE 以外に小さな罠もあるにはあって、問題文に書いてある通りの手順を守らないと最後に残るクッキーが違ってくるような気がする。行を取り除くには２列以上、列を取り除くには２行以上残っていないといけないという条件から、残り２行もしくは残り２列付近で手順が最終結果を左右するのではないかと思う。手順を守るように途中で書き直したおかげかは知らないけど、というか書き直しだけなら５回も６回もそれ以上でも行きつ戻りつしていたのだけど、ペナルティを出さずに AC だった。TLE を回避する手段は、まだ残っている行番号と列番号を記録して使用することと、行と列にある文字の種類と数を記録して使用すること。■E 問題「Prerequisites」。スタックに積んで順番に読むだけ。WA を出したのはひとえにあほだからです。もう読んだフラグを立てるタイミングを間違えた。そのタイミングで何かするのを帰りがけ順っていうらしい(聞いたことはあるよ)。■F 問題「Shortcuts」。とりあえず DP で解けるのはわかる。制約が１万以下とよくあるものより１桁少ない。２乗で１億、定数倍２分の１で 5000 万。言語アップデートにより「倍早い」こともある Ruby-3.2 ならワンチャンあるかという数字。時間内に提出したものは TLE だった。ああ無情。■F 問題。悪いのはもちろん Ruby ではない。実は途中で必要に迫られて DP 配列の次元を増やしていた。O(N^3) にはどんなチャンスもない。ツイッターで見ちゃったんですよ、ペナルティは 50 回まで考えれば十分だと。見積もってみれば 28 ビットで上限を突破しそうだったので 30 を上限にしてみたら通った。O(30*30*N) だから 900 万のレベル。大枠は完成していたんだから時間内に通したかったねえ。