Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

AtCoder Regular Contest 088

今回から余裕があれば自分の解法とか感想とかを書いていこうかと思う。
思考の過程を整理したり、解法を一度文章にまとめたりすることで競プロ強くなんないかなと淡い期待。

結果はCDEの3完で101位でした。

C - Multiple Gift

必要条件を徐々に広げていく感じで考察していくと、

  •  A_1 = X
  •  A_{i+1} = 2A_i\, (i\in\mathbb{N})

の漸化式で、 A_n\leq Yとなるような最大のnまで生成した数列が、条件を満たす長さが最大となる数列の一つだとわかる。よってこのnが解。
愚直に1つ1つ計算して長さを求めるとO(\log\frac{Y}{X})で通る。

D - Wide Flip

 N:=|S|とする。また、添字は0-basedとする。

制約から想定解法は O(N\log N)っぽいし、問題中で「最大の整数Kを求めてください。」とあったので、二分探索をまず疑った。

ので、 Kを固定してそのときにすべて0になるような数列にできるかを考えた。

  •  i=0, 1, \cdots, \min(K-1, N-K)の順で S_i = 1だったら区間[i, i+K)でフリップ。
    • この操作で S_0, S_1, \cdots, S_{\min(K-1, N-K)}0になる。
  •  S_0, S_1, \cdots, S_{K-1}がすべて0になれば、もとの数列は条件を満たす。
    •  \because  S_i=1\land i\geq Kならば、「区間[0, i+1)でフリップ→区間 [0, i)でフリップ」をすることでS_iのみの反転が可能で S_i=0にすることができるから。
  • 逆に S_0, S_1, \cdots, S_{K-1}のうち1が存在すれば、もとの数列は条件を満たさない。
    •  \because このとき、S_0=S_1= \cdots =S_{i-1}=0\land S_i=1となるi\in \{N-K+1, N-K+2, \cdots ,K-1\}が存在する。 S_{i-1} S_{i}を同じ数字にするためには少なくとも1回は区間 [s, i)(ただし s\in\{0, \cdots, i-1\})または区間[i, t)(ただし t\in\{i+1, \cdots, N\})でフリップする必要がある。しかし、 \max (i-0, N-i) \leq K-1 \lt Kより、そのようなフリップはできない。
    • (コンテスト中では直感で正しそうだったので、ちゃんと証明せずにコードを書いた)

これで条件を満たす数列かの判定ができた。判定にかかる計算量は O(N^2)で、二分探索も加味すると全体で O(N^2\log N)で間に合わない。

しばらく悩んだけど、次の事実に気づいた。

  • フリップ後に「S_i = 0」であるかは、 S_iに作用したフリップの回数 kに対し「 S^{(0)}_i + k = 0 \bmod 2」と等価。
    • ここで、 S^{(0)}_iはなにもフリップしていない時点での S_iを表す。

よってフリップの作用を累積的に計算していくことで計算量を O(N)に落とせる。よって全体の計算量は O(N\log N)になる。

解説読んだらこれよりスマートかつ O(N)での解法が紹介されてて天才か?ってなった。

E - Papple Sort

回文にできるかどうかの判別は単純なので、以降回文に並び替え可能であると仮定。

  • 「隣り合った2つの文字を入れ替えてソートするときの最小入れ替え回数」は転倒数に等しい

この事実を知っていたので、問題を見てすぐ、転倒数を求めることになりそうだなと思った。

ただし、転倒数を求めるには最終的にどのような数列を"整列"とみなすかを考えなくてはならない。今回の場合は回文は一通りとは限らないため、整列となる候補は1つとは限らない。

しばらく最適な回文が何かを考えてたらふと思いついた。(この部分の考察は解説とだいたい同じだったため省略)

BITを手元のライブラリで準備してなかったので転倒数はセグ木で求めた。どうやって計算するのかど忘れしたので無駄に時間かけてしまった。