脳log[20250201]

2025年02月01日 (土) [AtCoder] 今日は AtCoder Beginner Contest 391 があった。序列の範囲の上限付近で相応の歯ごたえがあり満足感もあった DE に対して、やるだけだった腑抜けの F がその位置で 500 点を与えられていることに、自分がその点数を獲得していないことに不満が隠せない。■A 問題 Lucky Direction。自分は連想配列で８通りの変換を書いたんだけど、４文字から４文字への文字置換で十分だったらしい。無駄に３分も使ってしまった。■B 問題 Seek Grid。答えが１つだけあると書かれているので、また、４乗が通る制約なので、素直にやる。４分かかったけどこれはしかたがない。むしろがんばっている。■C 問題 Pigeonhole Query。鳩ノ巣原理？ 最初巣から巣へ全部の鳩を移すのかと思っていたが実装を始めて勘違いに気がついた。鳩を１羽特定して巣から巣へ移す。巣にいる鳩の数を管理するのに加えて、鳩がどこにいるかも管理する。巣にいる鳩の数が１と２の間を行き来するたびに答えが変化するので、この数も追跡してすぐに答えられるようにしておく。■D 問題 Gravity。最初に書いておくと 44 分かかった。状況を厳密に定義するためなのだとしても、最近の自分の頭は +0.5 秒を適切に扱える明晰さを失っている。0.5 秒ってなんなんだよお前はいつ消えて俺はいつの状況を答えればいいんだよとキレそうだった。前回と前々回の ABC では実際にキレ散らかしていて問題を解くどころではなかったので、そこは良くなっている。まず列ごとに各ブロックがどの高さにあって下から何番目かを調べる。次に下から X 番目のブロックの最大高さを調べる。そうすると X 行消すのに何秒かかるかがわかる。わかる？ わかるということはわかるけどそれと実際にクエリに答えることは別の問題なのだった(消えるのは y 秒後か y+1 秒後か、それと 0.5 秒が問題)。サンプルがいつまでも合わない。あと X 行消すことができない場合に注意する。■E 問題 Hierarchical Majority Vote。セグメント木的な形をイメージする。セグメント木は二分木だけど３つ組の木そのものが問題になったものとして JOIG 2024/2025 本選 過去問-C 修学旅行 (School Trip)を最近解いた (#61675220)。まあいいや。解答の形としては根までマージを繰り返してから、選択的に葉まで下降して葉の数を数える。どういう情報を持ってどういうマージをするかはセグメント木の使い方そのもの。それをまとめるのに１時間 10 分かかったし、マージ部分のミスを修正するのにも６分かかった。こうなるとなんにも惜しくないのでやっかいな問題を解いた満足感の方が大きい。F 問題と違ってね。■F 問題 K-th Largest Triplet。小さくない N に対して３乗の組み合わせが問われているので、これが現代の Pairs かと絶望に襲われかけた。だけど K の上限は min(N^3,50万) なのであって、大きい方から順番に K 個の値を数えることができる。とりあえず A,B,C をソート。プライオリティキューで [N-1,N-1,N-1] から得られる値を起点にして K 個の値を取得しては最大３個の値を追加する。最大というのがポイントで、[i,j,k] をキューに追加しようとするタイミングは [i+1,j,k] と [i,j+1,k] と [i,j,k+1] の値を取得した３回あるので、たとえば i*N*N+j*N+k をキーにして重複を管理する。それだけで通ったのが納得いかない。21 分。F 問題の中で最弱なのではない、F 問題にふさわしくないんだよ。■ここ３回の ABC は極めて不本意な結果。簡単に解ける問題と解けない問題はいい。解けるけど時間がかかる問題にてきめんにやられているのが直近の３回。D 問題が簡単に解けないのが問題といわれればその通りだが、少し前まではこうではなかった。これが ABC の新しいスタンダードなのであれば、うーん、タイムアタックはつまらない。これまでも完走できてはいなかったけど、これまで以上に途中のある時点での順位が最終順位になるような状況が、得点がコンテスト時間のとり方(100 分)に大きく左右される状況がつまらない。ARC に活路を見出すこともできない中途半端な脳みそなので困っています。■E 問題。さっき書いた解法の後半、根から葉まで下降するパートは必要なかった。マージ部分が間違っていたから葉まで下降する必要がある気がしていたのであって、バグを取ったらその必要もなくなっていた。提出 #62311932 (AC / 221 Byte)。シンプルになった。最初からシンプルにすっきり解けないぼんやり頭が問題か？