AtCoder Beginner Contest 199（Sponsored by Panasonic）

最近C問題(たまにB問題も)難しくないですか？単に手を動かすだけじゃなくて、考察をちょっと挟まないとTLEしてしまう問題が増えている気がします。明確に計算量がオーバーするなって分かる問題はいいんですが、今回のC問題みたいな文字列(リスト)操作だと、どれぐらいの計算量になるのかイメージできなかった人は少なくないのかなと思います(私です)。

なので今回のC問題はすごくいい教材になりました。なんとかACできてレートも増えましたし。本番でフラグ管理思いついたの偉いぞ自分。

A - Square Inequality

やるだけですね。ちなみに僕はブラウザでAtCoder Easy Testを使ってサンプルケースを通せるかよく試してるんですが、コンテスト開始直後ってA問題の提出が集中して負荷高いからか、このスクリプトが碌に動いてくれないです。

これまではそういう時に自前でサンプル用意してテストしてA問題提出…ってやってたんですが、どうせ後からスクリプトなりで自動テストできるんだったら、負荷が落ち着くまでB問題解きに行っとく方が効率良いんじゃないかと思い始めました。開始後何分ぐらいでAtCoder Easy Testがまともに動くようになるのかのチェックも兼ねて、次回から試してみようと思います。

B - Intersection

$A_i$と$B_i$を頭から見ていって、xが取りうる範囲の左端Lと右端Rを更新していくだけなんですが、L=Rの時に答えが1になるというのを考慮しないまま提出しちゃって1ペナ喰らいました。最初何が起こったか分からなくて頭に？マークが浮かんでました。A問題B問題でつまづくと、焦りから後ろの問題にも響いてくるのでちゃんと確認してから提出したい…ってもうN回言ってますねこれ。

C - IPFL

文字列(リスト)操作の計算量を見誤りました。この問題ではT==2の時にスライス操作でSの前半後半を入れ替えるとO(N)の計算量がかかってしまいます。僕は最初O(1)でいけるのでは？と勘違いしており、TLEを出してしまいました。Pythonの計算量に関しては、このサイトが参考になりそうです。

ということで、明らかにボトルネックになっているT==2の時をどうするかということで、反転フラグだけ管理して、その真偽に応じて入れ替え対象インデックスを 加工してやればいけるのでは？と気づきなんとかACできました。

実際にACしたコードだとかなりごちゃごちゃと条件分岐しているんですが、上位勢のコードはめちゃくちゃ綺麗で参考になります。常々思うのは、剰余の使い方がとても綺麗だということです。zkouさんのコードとか、kyopro_friendsさんのコードが参考になりました。特にkyopro_friendsさんは、文字列の前半後半でX[0]とX[1]に分けて、T==2の時はスワップで反転を管理しつつ、T==1の時にa、bをNで割った商と余りでインデクシングして入れ替えてるのが綺麗だなと思いました。

D - RGB Coloring 2

解けませんでした。青diffだったんですね…

最初Union-Findで連結なグラフの集合を求めてごにょごにょやるだけで解けるのではないかと思ったのですが、それだけだとどの頂点とどの頂点がつながってるかの情報が欠落しちゃうので駄目でした。ただ一手目としては悪くなかったようで、hamayanhamayanさんの解説でも、連結成分の集合を求めた後各々に対してdfsで組み合わせ数を求めていく方針が説明されてますね。解説読んで勉強します。

ローカル開発環境を整えた話

最後に、コンテストとは別の話になるんですが、これまでPaiza.IOを使ってコーディングしていたのを、先日ついにローカル開発環境に鞍替えしました。エディタはVSCodeを使ってます。今はよく使う関数とかアルゴリズムのスニペットを整備中です。AOJのコースリストの各問題をやりつつ、強い方の綺麗なコードを拝借していこうと思ってます。

また、online-judge-toolsを使ってサンプルテストと提出の自動化もできるようになりました。yukicoder、Codeforcesも対応しているので大層嬉しいです(Codeforcesの自動提出は対応されてないようですが)。ただ肝心のABC199中にテストケースダウンロードと提出ができなくなるというトラブルが発生し、結局手動でサンプルファイルの準備とブラウザからの手動提出で対応しました。原因については次回以降に再現確認も兼ねて調査したいと思います。

以上です。