脳log[20250427]

2025年04月27日 (日) [AtCoder] 今日は AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）があった。F のデバッグのためにあと５分あれば時間内に通っていた。無念。■A 問題 Odd Position Sum。やります。最近古い ABC の A 問題 B 問題を埋める(ことに意味を付与する)ために Haskell を書いてるんだけど(書いてるだけでまだ提出していない)、これが実に難しい。「やります」じゃないんだよ。七転八倒してやっとなんとかなるレベル。C 問題にはまだまだ手が出ない。Ruby だから所要１分半。■B 問題 Four Hidden。正規表現でうまくできないかなと思って書いたけど、無駄に高機能なものを持ち出しただけに終わった。所要４分。■C 問題 403 Forbidden。ABC401 から続く HTTP ステータスコード。閲覧権限をメモしておいて答える。「すべてのページ」の閲覧権限を別枠で持たなければいけないことに注意する。全ページ個別に閲覧権限を付与してまわってはいけない。所要６分。■D 問題 Forbidden Difference。配点が +25 点なだけあってきっちり WA を出した。D で割った余りでグループ分けをして D で割った商の連続についてそれぞれどういう間引き方をするのが得かを考えた。何を勘違いして WA を出したか。偶数番目を間引くか奇数番目を間引くかの２択だと思ったんだよね(A 問題がこれへの布石だったならあまりにも策士)。D=1 で A.uniq=1,2,3,4,5 であるとき、B.uniq=1,3,5 か B.uniq=2,4 が答えの候補のすべてだと思ったんだけど、実は B.uniq=1,4 も B.uniq=2,5 も答えになり得る。何が答えになるかは 1,2,3,4,5 それぞれの重複度による。DP をしないといけなかった。感想を見てると D=0 のとき %D や /D で RE を出す罠もあったらしい。でも問題文にしっかり「非負整数 D」って書いてあるよ。MEX が典型なんだけど、否定で定義されると理解が１ステップどころか２ステップも３ステップも遅れるので、今日も「非負整数……非負…非負……ゼロ以上ってことね」と理解に時間を費やしていたおかげで、%D を書くときにすっと場合分けができた。所要 20 分＋１ペナ。■E 問題 Forbidden Prefix。スマートには解けなかった。結構力押し。クエリを先読みして X の集合と Y の集合をソートしておく。X の各要素について、どの Y 要素の接頭辞になっているかという範囲を二分探索で求めておく(演算は普通に String#<= と String#start_with?)。ここまでが事前準備で、クエリに沿って削除された Y 集合の範囲と、まだ削除されていない Y 集合の要素を２つの BIT で管理しながら答えていった。所要 31 分。■F 問題 Shortest One Formula。1 と 11 と 111 と 1111 の構成方法は確定している。あとは１から N までボトムアップで最短の積と最短の和を構成していった。積と和を区別しているので積と和を構成するにあたり括弧の要不要の判断が簡単にできる。また、積は a*b、和は a+b という２項演算だけを考えた。例えば a+b+c という形が最短になるというなら、それは d(=a+b) の最短と c の最短の２項を組み合わせるなどして構成することができる。和の構成は n/2 通りの総当たり。積の構成は√n通りの総当たり。終了１分前のこの提出 #65289442 の何が WA の原因か。24 行目の文字列リテラルで括弧の付け方を間違えている。それだけ！ くやちい！ ５分オーバーで AC (#65291201)。所要 43 分。■結果出た。コンテスト成績証。690 番 1665 青パフォ。F 問題がぎりぎりで通っていても 100 番 100 パフォ上がるくらいの差みたい？ E を通した時点で 40 分弱残していたのがわりと早かったのだな。じゃあ時間外でも F が解けたということが素直に喜べる。■■■F 問題。最初から積の最短と和の最短を持とうとしていたわけではない。必要がなければわざわざ分けたりはしない。最初は最短の文字列を検索して + があれば括弧で括って掛け算に利用したり、括弧なしで利用したりしようとしていた。でも (1+1)*(1+1) だったら + があるけど括弧なしで掛け算に利用できる。パースする？ それは明らかな無駄。文字列ではなく和クラスと積クラスをネストさせて最後に文字列化するのがいいでしょう。もうひとつ。ある数を積で表す方法と和で表す方法の２通りがあるとき、括弧で包む(くるむ)必要がない積の形式の方は和の形式の最短より１つ長くても積を構成する場合に限って有利な立場にある。こんな感じで２通りの意味で積の最短と和の最短を分けたいなという気持ちになる。それでうまくいった。■■■E 問題。Trie っぽく解き直し。提出 #65384945 (AC / 534 Byte / 1885 ms)。BIT 解の方が (1711 Byte / 578 ms / 932996 KB) だから、短いけどかなり遅くなった。再帰関数で Enumerable#group_by を呼ぶのがぜいたくなのだろうか。なにげにメモリ消費 900 MB がやばいね。木を再帰的に下降しながらその部分木の接頭辞となっているクエリ番号のうちもっとも小さい(早い)ものをメモしていった。そうすると Y 集合に属する文字列が見つかったとき、その文字列を答えに数えられるクエリの範囲が求まる。Ruby での提出を眺めると、ちゃんと Trie が扱えている人たちは 500 ms 台に収めているらしい。