感想戦 ; ABC430

目次

はじめに

OMCG002 に参加しました. OnlineMathContest は少し前からチラチラ見ていたのですが, これまでは都合が合わず, on time でコンテストに参加したことはありませんでした. 今回の OMCG は有志コンテストで Unrated でしたが, 土曜日かつ 10 時間という条件だったので参加してみました.

結果的には A, B の 2 問正解で, 順位は 105 位.

OMCG002 の解答結果

100 点の A, B だけ解いて離脱しようと思いましたが, A がなかなか解けず. 一旦 B を解き, A も何回か誤答を繰り返し, 最終的に何とか正答できました. 実は図形の問題は得意ではなく, 受験生の頃に 大学への数学 の図形問題を集めた増刊号に取り組んだ記憶がよみがえりました.

さて ABC430 です. 今回から Codon が使えますので, 計算量が気になるときに試してみたいです. ここのところ負けが続いているので, 何とかしたいところです.

今回は B 問題から見ていきます.

B - Count Subgrid

atcoder.jp

与えられたサイズでグリッドを切り取ったとき, 何種類あるか? という問題. 250 点とちょっと難しめ. 重複させずに数えるときは set() を使うのが常套手段ですが, 例えば切り取ったグリッドを「リスト」で表現していると, そのまま set() に放り込むことはできません.

私は, 切り取ったグリッドを各行をつないで 1 つの文字列にして, それを set() に入れました. 文字列操作は計算コストが大きいですが, 今回の制約なら何とかなるという見通しです.

13:14 にAC.

C - Truck Driver

atcoder.jp

さて, 問題はここからです. 最初は尺取りでできるかな? と思ってコーディングしてましたが, 普通の尺取り, すなわち

  • 条件を満たす間は r をインクリメント
  • 条件を満たさなくなったら l をインクリメント

ではすべての場合を数えきれないことに気付きました (ここまでも結構時間が掛かりました)

ならば累積和を計算して, 任意区間の "a" と "b" を数えようとしましたが, O\left( N^2 \right) の時間計算量では間に合いません.

コンテスト中にできたのはここまでで, 結局のところ解けませんでした (;_;)

終了後に解説を読み, 単調増加なので二分探索を使えばよいことを知り, コンテスト終了後 18 分で upsolved. まだ基本が身に付いていないことを実感させられた問題でした.

D - Neighbor Distance

atcoder.jp

「部分的に更新していく」ということは分かりました. が, リストを常にソートされた状態で持っておく必要があるので, 新しい X_i を挿入する場所を効率よく探すにはどうすれば良いか? と考え, そこから先に進めませんでした.

ここで私が見落としていたのは, D 問題の実行制限時間が 4sec ということ. 以前にも実行制限時間を見落としていたことがあり, それ以来, 必ず実行制限時間を確認していたのですが, 今回は焦りのせいで見落としていました.

さて, コンテスト後に解説を参考にしながら, データは list() で持ち, 新しい X_i を挿入する場所は bisect で探す方針でコーディングしましたが, 結果的に TLE.

Twitter で「SortedSet を使った」というのを見掛けたので, SortedSet を使ったら何とか AC できました. ただし実行時間は 3884ms とギリギリ.

試しに, 最初にすべての X_i を並べてそれぞれの最短距離を求めてから, 逆順に減らしていく方針でもコーディングしてみました. 実行時間は 3400ms と 1 割くらい速くなりました.

E - Shift String

atcoder.jp

備忘録的に書いておきます. 解説では z-algorithm の解法が紹介されていましたが, Twitter で CPython なら find() で通る と見かけました. そこで, find() を使った速度を比較しました.

処理系 結果 コード
PyPy AC x 36, TLE x 16 #70655102
Codon AC x 40, TLE x 12 #70655121
CPython AC x 52 (41ms!) #70655131

確かに CPython が圧倒的に速い. 「大抵は PyPy が速い」との説明を見ることが多いし, 実際正しいのだと思いますが, CPython が速い場合もあるんですね.

結果

AB 2 完でしたが, B 問題の 250 点に救われて, 前回の ABC429 よりはパフォは上でした.

今回の学び.

  • 実行制限時間や制約はきちんと確認しよう
  • 単調増加は二分探索で探す (ちなみに極値があるときは三分探索)
  • ソートされたデータを使うときは, 素直に SortedSet を使う

来週以降もめげずに頑張ります.