見出し画像

競プロ参戦記 第3回「剰余の世界」Codeforces #506

Codeforces の競技プログラミングの大会に参加しました。簡単に要約と解説をしていきます。

問題文は端折っているので、厳密な条件や制約などはコンテストのページを見てください。


A. Many Equal Substrings

問題:文字列 S がちょうど K 回出現するような最短の文字列を求めよ。

例えば S=ababa, K=3 なら ababababa 、例えば S=aaaa, K=2 なら aaaaa 、といった具合です。

+ ababa
+ __ababa
+ ____ababa
= ababababa

つまり S を2つ並べたときにどのくらい末尾の「再利用」ができるかを計算して、再利用できる部分を除いて繰り返せばOK。(Sの先頭 n 文字) = (Sの末尾 n 文字) が最大になる n を求めます。文字列 S の長さの上限が 50 なので全探索でいいです。

Div.3 (初心者向け) のA問題にしては骨がある問題でした。

提出:


B. Creating the Contest

問題:難度 a_i の問題が N 個ある。コンテストで出題するために、この中からいくつかの問題を選びたい。ただし、どの問題も、その次の難度の問題との難度差が2倍以下になるように選ばなければいけない。選べる問題数の最大値を求めよ。

この問題の考えるべき点は、ある問題 a を選んだら、他の問題の選び方に制限がかかるところにありそうです。なので、すべての問題 a_i について、それを選んだときの最大の選び方がどうなるかを具体例で考えてみました。すると次のことが分かります。

問題 a_i, a_(i+1) の難度の差が2倍以上ある (2 a_i < a_(i+1)) と、この2つは同時に選べません。ここを「難度の壁」と呼ぶことにしましょう。条件から、壁の内側の問題はすべて選べる、むしろ選ばなければいけないことが分かります。飛び石のような感じですね。結局、難度の列はいくつかの区間に分割されます。これらの区間の長さの最大値を求めればOK。

200 300 400 |壁| 900 1100 |壁| 2300 2400 

提出した実装で、区間の分割を綺麗に書けたのが個人的にポイントです。以前は、区間 [L, R) が見つかったときの処理をループの中と後ろに2度書くような実装をしてしまっていましたが、ループを R=N まで進めることで1回にできました。

提出:


C. Maximal Intersection

問題:数直線上に区間が N 個ある。どれか1つを取り除いたときの、残りの N-1 個の区間の共通部分の長さの最大値を求めよ。

区間 [l, r] の共通部分は [max(l), min(r)] で求まります。これは区間の左端にだけ注目すると、左端の最大値 max(l) より後しか共通部分に残らないことから分かるでしょう。右端についても同様です。

どの区間を除外するか、というの考えるのは難しそうなので、ループを回してすべて試すことにします。このとき、除外しない区間の共通部分が高速に求まればOK。

これはいわゆる RMQ (range minimum query) 問題です。セグメントツリーを使ったり平方分割したりしても解けますが、今回は累積和を左右からやれば解けます。

除外する区間より「前」の区間を [ll, rl] 、「後」の区間を [lr, rr] で表すとしたら、最終的な共通部分の左端は max(max(ll), max(lr)) といえます。max(ll) と max(lr) はそれぞれ累積和で求まるので O(1) です。右端も同様。

提出:


D. Concatenated Multiples

問題:正の整数 n, m について、n, m の10進数表示を連結した数を cat(n, m) とする。いま正の整数が N 個ある。これらから選んだ順列 (n, m) で、 cat(n, m) % P = 0 となるものの個数を数えよ。(ただし n ≠ m)

cat 関数は cat(12, 345) = 12345 のような操作です。数学的に扱いやすいように再定義します。

正の整数 m の10進数での桁数を len(m) とおきます。例えば len(9) = 1, len(10) = 2, len(314159) = 6 です。cat(n, m) は cat(n, m) = n * 10^len(m) + m と表せます。

答えが剰余に関して求まるものなので、まず剰余の世界に行きます。このとき私が行ったのはWAの世界だったと気づくのはもっと後になってからです。条件 cat(n, m) ≡ 0 (mod P) を式変形すると

n * 10^len(m) + m ≡ 0
n * 10^len(m) ≡ -m
n ≡ (-m) / 10^len(m)

です。うまく変数が分離できたのでハッシュ結合にいけます。各 m について右辺の値 X = (-m) / 10^len(m) を計算して、ハッシュテーブルから n≡X となる n の個数を調べれば高速に数え上げが可能。楽勝かな?

ここで P (本来の問題文では K ですが筆者が脳内変換した) は素数ではないので除算が一意になりません。不正解です。

提出 (不正解):

除算を避けるために式変形を一段階戻して、n * 10^len(m) ≡ -m をみます。len(m) の値は 1~9 のどれか。10^len(m) の値を全列挙してしまえば左辺の m はないも同然で、次のようにハッシュテーブルが作れます。

dp [ l:mの桁数 ] [ r:剰余 ]
  = (n * 10^l ≡ r となる、与えられた整数 n の個数)

各 m に対して l = len(m), r = -m とおくと、条件を満たす n の個数は map[l][r] です。

最後に n = m となるケース (同じ数を2回選んでしまうケース) を除外すれば完了。ついにACの世界に来ました。そこはコンテストが終わった世界でもあります。

提出 (コンテスト終了後):

おわりに

C完です。B, C がスムーズに解けたし D も自力ACできたので上々。


追記:E/F問題も解きました。


この記事が気に入ったらサポートをしてみませんか?