脳log[20240128]

2024年01月28日 (日) [AtCoder] 昨日は ABC338 があった。当たり前に解ける問題を当たり前に解いてレートが上がっても微妙な気持ち。それって現在のレートが下振れているだけだから。F も G も解けない問題ではなかった。F はどうやって典型に落とし込むかだと思った。@chokudai さんが以前に書いていたように、負辺を前処理で取り除けると思う。それができるための負閉路がないという制約。必ず終わりがある。だけど前処理がすっきり見通せないから、大変でもすることがわかりやすい G 問題に、時間内は主に取り組んでいた。G を通してからふりかえりを含めて書き足す予定(以降更新されないフラグ)。■E 問題ではこの問題を思い出していた。ARC076-E「Connected?」(20211112)。昨日の水 diff に対してこちらは黄 diff だけど、同水準の知識で解ける。■■■@2024-01-30 フラグを折っていく。ABCDE のふりかえりと G の精進を。■A 問題「Capitalized?」。Ruby には String#capitalize メソッドがあるので……。だけど問題の定義と Ruby のメソッドの仕様の整合を確かめる手間で、もっと曖昧さが少ない低レベルのメソッドを使うことも現実的な選択肢ではある。低レベルとは言えないけどよく知った正規表現で書いた。文字コードを見るなら特定の１ビットで判別できる。■B 問題「Frequency」。フリークワンシィ。集計してから最初の文字を見つけた。うっかり１ステップで書こうとすると苦しむかも。max_by がぴたりとはまるらしく(#49693254)、苦しまずに解決する方法がちゃんとあったようだけど、Enumerable#max_by の暗黙の仕様に頼っていたりして(「該当する要素が複数存在する場合、どの要素を返すかは不定です」というのが明文化された仕様)、自分は思いつかなかったな。それは言い訳で、添字をペアにして比較のキーにすれば仕様に則って確実に１ステップで答えが出せた。■C 問題「Leftover Recipes」。一瞬詰まった。DP かと思わせて総当たりができる。一方の個数を決め打つ総当たり。ゼロ除算は避ける。■D 問題「Island Tour」。環状に繋がった島がある。ツアーで島から島へ移動するルートは右回り左回りの２通りが考えられるけど、どちらが右回りでどちらが左回りかはどうでもよくて、橋が１つ封鎖されていると必ず一方に固定される。封鎖する橋を決めたときの影響を単位時間で求めるために、影響の変化量を記録してその累積和を観測する。一発で通ったけど添字でバグらせなかったのはただの運。慎重に書いて祈って提出した。■E 問題「Chords」。スタックです。頂点を順番に見ていって出て行く弦、入ってくる弦を管理して交差を判定する。変数名で困った。arc は弧だから弦は何だろうと。それが問題名の chord なんだろう、きっと。自分では string かなと考えたけど、あまりに紛らわしいし、弦違いっぽくもある。code や cord に比べて余分な文字がくっついてるのがへその緒っぽさを感じさせるけど、あれは umbilical cord らしい。エヴァで聞いた音。さっき類似の過去問を紹介したけど、その問題を解いたときに「ということに気がついたら、あとはなんとかなる」と書いていた部分がなんとかならなくて２回も WA も出したのはどうかしている。あほになってんじゃねーの。■G 問題「evall」。することはすぐにわかる。それをするのがすんごく大変なだけで。考える範囲は両端が数字であるような範囲。まずは + で区切ってみる。+ の左にある数字の数と、+ の右にある数字の数がわかれば、主客転倒で + で囲まれた数(式)の寄与がわかる。次に考えるのは、範囲が + で囲まれた内部に端を発して外部に出ていく場合。範囲の内外で数字がちょん切られるので扱う値が変わってくる。だけど範囲の一方の端を決め打ったときの値とその寄与は同様に求められる。範囲の両端が + の内側にある場合の寄与は、これは累積和の問題として単独で D 問題あたりにでもなりそうな難易度の問題。ここまで触れてこなかったけど、+ で囲まれた内部は単独の数字ではなく * で連結された積の場合がある。ここまでと同じように * で分割して左右からの累積和(累積積？)で全体への寄与を求めるんだけど、このあたりからワーキングメモリが枯渇してきて全体を把握するのが困難になる。スラッシングというのかな、何をするにも復帰に時間がかかり、間違えて手戻りが発生し、ちっとも先に進めなくなる。最終的に自分はクラスを使って問題を分離して個別に対処することになった。そうするとあるレベルで考えているときに別のレベルのことを考えずに済む。メソッドを呼んで別のレベルの処理結果を得るだけにすると、大きくなりすぎたスイッチングコストがまるまる節約できる。■提出 #49805072 (G 問題 / AC / 1554 Byte / 825 ms)。サンプルが通りさえすれば他に特に罠はなかったみたいだけど、答えの突き合わせに C++ で提出が早かったこちら(#49712435)を使わせてもらった。実行結果にしか興味はなかったけど、ちらりと覗いてみた solve 関数のシンプルさがすごかったよね。しかしあまりにも最適化されすぎていて、冗長さが足りなくて、自分には書けないし理解できない。そんな簡単そうに解ける問題じゃなかったよ。この構成をあきらめたから、クラス化による問題の整理分割に行ったのだ。■コンテスト成績証。自分のすべての提出。ABCDE の５完でぎりぎりの青パフォ。もう書いたけど、これで上がるのは現在のレートが下振れてるだけなんよ。■G 問題。X で(自賛を)見かけたので探してみたこちらの提出 #49757867 (tanakh さん / Rust)。class を使って構造化するならこのレベルまで突き詰めて抽象を取り出して汎化したいよね、というお手本。あと変数名も適切でかっこいい。累積和のことを prefix sum と呼ぶこともあるみたいなので、今回のように色々な累積和を扱うときにああいう呼び分けはあまりに適切。■■■G 問題。お手本にならって再構成してみた。提出 #50091522 (TLE×7)。残念 TLE。一応、数字の列を１桁ずつ分解してオブジェクトを再帰的に構築するのは避けて、* と + で分解した数字の列からループを回してオブジェクトをひとつだけ作るようにしたんだけど、演算(+ と *)のたびに新しいオブジェクトを作るのがまだまだ負担だったか。前回の提出では + の数だけオブジェクト数が節約できている。あと eval も重い。だけど evall という問題名だから eval したくなるのはしかたないよね。■提出 #50102025 (AC / 1127 Byte / 1759 ms)。通った！ ネックは gsub だった(gets.gsub(/\d+/){ "Num.from_s('#$&')" })。たとえば入力が最長の１メガのとき、演算子と数値が半々なら１桁の数字が 500 キロ個ある。gsub メソッドが入力の 1 を Num.from_s('1') に置き換えるなら、変換後の文字列長は８メガになる。そしてそれを eval する。遅い。Num.from_s メソッドを１文字のローカル変数にキャッシュすることで文字列の全長を抑えたら、だいたい倍くらい速くなって TLE を免れた。ちなみに Object.const_missing を使うことでさらに縮めるアイデアもあった。1 や 123 を N1 や N123 に置き換えるのだ。だけど汚い方法でありながらタイムの改善が微々たるものだったので不採用にした。+ メソッドと * メソッドをそれぞれ +=、*= メソッド相当の実装にするアイデアもあった。これもコードを歪める一方で大した改善ではなかったので不採用。せっかくきれいに再構成しているのだから、ダーティハックはお呼びでない。