読者です 読者をやめる 読者になる 読者になる

ぶていのログでぶログ

思い出したが吉日

AtCoder035を解いた(その3)

buty4649.hatenablog.com

前回解けなかったAtCoder035のCを解き直した。

マスクビット列の生成を文字列 -> to_iしていて(("1" * n).to_i(2)) 遅かったので、Integerで作るようにした。 n個の連続した 1を作るには 2^(n-1)-1 すればいい。 前回よりも解ける範囲は増えたが、やはりTLEになってしまった。。

abc035.contest.atcoder.jp

そうしたら、前回の記事に

C問題、「いもす法」というヒントをコメントします...!

というヒントを頂いた。

いもす法 - いもす研 (imos laboratory)

今回の問題の場合、オセロを反転させる範囲を矩形関数として見ることができるので、そこに利用する。 これを使って解いたところ一発で通った!!

abc035.contest.atcoder.jp

野生のsuzupyありがたやぁ〜 🙇

↑で解けることがわかったので調子にのってAWKでも解いてみたw 解法がわかっていればAWKでも解けないことはないですね。

abc035.contest.atcoder.jp