脳log[20240114]

2024年01月14日 (日) [AtCoder] 今日は ABC336 があった。コンテスト成績証。自分のすべての提出。ABCD の４完でレートは横ばい。EF がどちらも難しかった。ではふりかえりと F の精進を。■A 問題「Long Loong」。ループを回せますかという問題。■B 問題「CTZ」。count trailing zeroes. zero の複数形は -s と -es が並記してあるのでどっちでもいいのかな。じゃあト・メイトウ式で。文字列化して /0*$/ でマッチさせた。ループで求めるなら、N が 0 より大きく N を 2 で割った余りが 0 である限り N を 2 で割り続けて回数を数える。■C 問題「Even Digits」。去年の年末にこの問題を解くやり方をどこかで読んだ気がする(追記：先週のことだったらしい。「まさかこの発言の一週間後にフラグ回収すると思ってなかった」 自分もその発言を読んでいましたよ)。５進数で N を数えて各桁を変換した。他の人の提出を見ると変換に String#tr を使ってる人は全然いなくて、みなさん十進数として再解釈してから×２をしているようだった。それは……かしこいなあ。■D 問題「Pyramid」。本日はこの問題で終了してしまった。書き始める前には、ピラミッドの中心に据える A 数列の値(これが k になる)とその左右にある要素数だけでピラミッドの大きさが決まると思っていたけど、サンプルの１からすでに答えが合わなかった。たとえば中心の隣の要素が中心より２以上小さかったらピラミッドとして成立しない。なので左右から独立に DP をして、左(右)の要素が左方向(右方向)に作れるピラミッドの大きさ＋１を上限とした(もちろん中心の値も上限のひとつ)。■E 問題「Digit Sum Divisible」。桁和の種類はかなり少ない。桁和が固定できると各桁に配置した数字を桁和の余りで分類できるから、並べ替えを考えずに済んで考えるべき状態数が減る。だけど各桁の使用状況と現在の桁和の合計とを状態として、決め打った桁和を目指す DP が書けなかった。それで間に合うかわからないし、持つデータの型と遷移もよくわからない。制限時間 10 秒はすごい。これをどう評価するか。C++ でもそれなりに時間がかかるので定数倍で劣る Ruby ではループ回数に比例して遅れが積み重なって到底間に合わないと見るか、それとも、スクリプト言語に配慮した結果の 10 秒なのか。■F 問題「Rotation Puzzle」。半分全列挙だとどこかのツイートだったようなもので読んでしまった。BFS をするには 20 回の操作回数は多すぎるなあとはコンテスト中に実装してわかっていた。そこから半分全列挙が出て来ない。そうだとわかれば実装するだけなんだよね。提出 #49322044 (AC / 557 Byte / 2792 ms)。配列を Hash のキーにすると答えを間違える。キーにするためにつど文字列化するとコードテストで制限時間をわずかに超える。だから文字列を操作することにしてそのまま Hash のキーに使えるようにしたら間に合った。その後、やってることは同じだけど２つの改善で 891 ms になった(#49349630)。