最終更新: 2021-04-06T17:58+0900
昨日あった ABC。今晩には ARC があるので復習が忙しい。
正規表現を乱用する問題だと決めつけて考えた。使える限り最善でなくてもかえって難しくなっても正規表現を使う。
パターンには改良の余地がある。たぶん /^([a-z][A-Z\n])+$/ で良かった。
$ は改行の前でも文字列の末尾でもマッチしたと思ったけど、フラグの影響がどう出るかが不確かだ。そして Ruby のフラグは JavaScript のフラグと比べてあべこべな雰囲気がしてわかりにくい。
入力が英大文字小文字だけだから大小の判別は１ビットを見るだけでいいんだけど、正規表現だから関係ない。
C 問題にしては……と疑いをもったが、テキトーに大きい桁を与えてもいけるみたいだったので問題の通りに関数 f を定義してシミュレーションした。本当はテキトーに大きいだけだとすぐに桁数の少ない値に収束してしまいかねなくて、そうではない嫌らしい値が与えられるかもという疑いがまだあったのだけど、とりあえず投げてみるスタイル。
最近誰かがツイートで Integer#digits メソッドに言及していたので初めて使ってみた。適所では？ そういえば D 問題でも使っていた。
やってきました因縁の D 問題。前回の虐殺劇が記憶に新しい>20210206p01.02。今回も E 問題が緑色なのに対して D 問題が水色だったりして、正答数に逆転があったもよう。
あれ？ やるだけ？ という感想はあまりに素直。たしかに優秀な人は目をつぶっていても答えにたどり着けるのかもしれないが、凡人は周到に落とし穴を探し出さなければいけない。
それは１の位についてだけ当てはまらない。基数が３でも４でも５でも、数１は０より大きい１番目の数で変わらない。
そしてこれが、基数の種類を答える問題でないことの傍証になる(そういう誤読が多かったらしい)。無限大の答え方が問題文中にないからだ。
二分探索の下限に d+1 を、上限に M+1 を設定していたのだけど、M+1 の方が d+1 より小さいことがあるから、答えを導く引き算の結果が負の数になるケースがあった。
手で計算しているときは自然と自然数の範囲でものごとを考えてしまって例外ケースを無視してしまいがち。
早期に AC を得ていた複数の人が上限を定めない二分探索を行っていたようだ。kotatsugame さんがこの奇妙な二分探索の振る舞いについてツイートしていたので存在は知っていたが、自分で使えるほどには知らないし思い出さない。
7 WA のあとの AC。どちらの落とし穴もテキトーな入力を与えて出力を見るデバッグで発見した。１桁のケースはタイプするのも簡単だし、それでいて境界に近くてバグが潜みがち。嗅覚を働かせよ。
えびま @evima0
(D 実はもともと「9 1」っていうサンプルがあったんですが、出題の意義が 1/3 くらい消滅する (「1 9」だと 2/3 消滅) ので消してもらいました) https://t.co/NNcbAu6GjF
このツイートはもっともで、そうでなければ D 問題としては易しすぎて出題されなかったと思う。といってもこれだけいくつも罠があって目配りが要求されるなら、AGC の A 問題といった風情もある。
自分より上位の人は仮に D 問題の罠にはまったとしても、さくっと E 問題を片付けてから帰ってきて、結局 E も D も通してしまうというムーブができてしまう。(そもそも罠にはまらないか)それができるからこそそのレイティングなのだ。自分がそれをやろうとすると虻蜂取らずになるのが目に見えているので、１時間かけて D 問題を通しました。今回の成績はABCDの４完最遅レベルでレートは横ばい。
競技プログラミングをするフレンズ @kyopro_friends
フェネック「もともとD問題でXが1文字のケースを、アライさんは2個か3個しか用意してなくて、それだとWAのケース数でコーナーケースがバレそうだからたくさん増やすようにアドバイスしてみたんだけど、どうだったかな？」https://t.co/FxcvbhUJNL
AC が出るまでは WA の数を見て方針を疑ったり挫けそうになったりしたけど、１アイディアで 7 WA が 1 WA にまで減ったりしたから、まあこういうことなんだろうと予想はしていた。まんまと手のひらころころ。
プライオリティキューを書くだけの問題。まあその「書くだけ」ができなくて 2 WA するのが自分なのだけど。
……だと思ったら、Ruby で最も速い複数の提出が Hash を待ち行列に使っていた。keys.min で最小値を都度取り出す使い方で、それでいて速い。えええ？
あと、久しぶりにプライオリティキューを書いたから速度改善テクニックを１つ忘れていた。ヒープを整理するときに都度都度要素を交換しながら上昇(下降)するのでなくて、ローテーションする感じで、いくつかの要素を順番にスライドさせてできた空きに追加要素を置くのがいい。