AtCoder Regular Contest 113 A,B,C,D,E問題メモ

AtCoder Regular Contest 113

怒濤の速解き勝負回。

AとかBとか、別にスクラッチから考えても答えにはたどり着けるけど、 既に性質を知っていたら数分がさらに短縮され、それが今回の場合そこそこの差を分けた感じがある。

A - A*B*C

• 整数 $K$ が与えられるので、$A \times B \times C \le K$ となる正整数の組 $(A,B,C)$ の個数を求めよ
• 順序が異なるものも異なる組として数える
• $1 \le K \le 2 \times 10^5$

全探索。$O(K^2)$ ではなく $O(K \log{K})$ になる。

$A=1,2,3,...$ と決め打ったら、$B \times C$ の上限は $\dfrac{K}{1}, \dfrac{K}{2}, \dfrac{K}{3},...$ となり、次に $B$ を決め打つ範囲はどんどん狭くなっていく。
たとえば最後の方の $\dfrac{K}{2} \lt A \le K$ の範囲では $BC=1$ しかあり得なくなるので1通りに決まったりする。

全体として $O(K \log{K})$ で $A,B$ を全て決め打てるので、各場合の $C$ の範囲を足し合わせればよい。

高速化の例として、$A$ を決め打つ範囲を $1～\sqrt[3]{K}$、$B$ を決め打つ範囲を $1～\sqrt{\dfrac{K}{A}}$ の範囲にして、あとはそこから求まった $C$ とあわせて3つの数を並べ替える場合の数を求める、という方法もある。

Python3

B - A^B^C

• 正の整数 $A,B,C$ が与えられるので、$A^{B^C}$ の1の位を求めよ
• $1 \le A,B,C \le 10^9$

1の位の数なんて10種類しか無いんだから、10回も繰り返せばどこかでループする。
$A$ の1の位の数が何回でループするか求めて、それが $k$ 回なら、$B^C$ は $\mod{k}$ で考えてよくなる。

ただし $B^C \equiv 0 \mod{k}$ になったら $k$ とする。

フェルマーの小定理から考えると、$10=2 \times 5$ なので、$5$ と互いに素な数 $a$ に対して $a^{5-1}=1$ となり、多くの数は2周期や4周期になる。
そうでない数も調べれば、4乗すればどの数も必ず元に戻ることがわかるので、$k=4$ と決め打って実装してもよい。

Python3

C - String Invasion

• 長さ $N$ の文字列 $S$ が与えられるので、以下の操作を行える回数の最大値を求めよ
• 操作
  • 'aab' のように最初の2文字が一緒で3文字目が異なる連続した3文字を選び、'aaa' のように3文字目を他の2文字と同じ文字に置き換える
• $3 \le |S| \le 2 \times 10^5$

直感的に思いつく方法がそのまま正解になるけど、それをスムーズにコードに落とし込むのにちょっとだけ慎重さが必要。

タイトルのInvasion（侵略）の通り、1回操作を行った箇所は1個ずつずらして末尾まで繰り返せる

accept → acccpt → acccct → accccc

2文字連続したブロックが複数ある場合、右の方から先にやるのがよい。上書きされた文字を再度上書きしなおすことで、操作回数を稼げる。

anerroroccurred  →  anerroroccurrrr  →  anerroroccccccc  →  anerrrrrrrrrrrr
   ~~   ~~ ~~                   ~~~~              ~~~~~~~         ~~~~~~~~~~~~

ただし、侵略中の文字と同じ文字があった場合、そこに対しては操作できないので注意。

                          次、ここに対しては操作できない
aabcabc  →  aaacabc  →  aaaaabc
~~~           ~~~           ~~~  

Python3

D - Sky Reflector

• $N \times M$ の各マス目がある
• ここに $1$ 以上 $K$ 以下の整数を1つずつ書き込み、数列 $A,B$ を以下のように決めることを考える
  • $i=1,...,N$ に対し、$A_i$ は $i$ 行目のマスに書かれた整数の最小値
  • $j=1,...,M$ に対し、$B_j$ は $j$ 列目のマスに書かれた整数の最大値
• 数列 $(A_1,A_2,...,A_N,B_1,B_2,...,B_M)$ としてあり得るものの個数を $\mod{998244353}$ で求めよ
• $1 \le N,M,K \le 2 \times 10^5$

割と数列をどういう風に決めたって、書き込み方を上手いことすれば成立させられちゃう感じがする。
できないものから考える。

A\B| 10 5
---+-----    これは大丈夫
 5 | 10 5
 2 |  2 3

A\B|  5 2    これはだめ
---+-----
10 |         ←この行のどこかには10を置かないといけないが、
 5 |           どの列もそれ未満の数字が最大値となっており置ける列が無い
       ↑
       この列には2以下の数字しか置けないのでどのAも2以上になるはずが無い

$A$ の最大値が $B$ のどれよりも大きかったり、$B$ の最小値より大きい $A$ があったりしてはいけない。（言ってることは一緒）

ここは、$A$ の最大値を固定すると見通しがよくなる。$k$ とする。

• $A$ には $k$ を必ず1つは使い、$1～k$ のみを使って構成する
• $B$ には $k～K$ のみを使って構成する

これさえ満たしていれば、大丈夫。

具体的な構築の仕方
A\B|  k+1 k+2 k+3
---+-------------
 k |   k  k+2 k+3    Ai=k である1行を選び、どこか1マスに k, それ以外にはBの示す最大値を入れる
k-1|  k+1 k-1        それ以外の1行には、さっき k を書いた列にBの示す最大値、それ以外のどこか1マスにAの示す最小値を入れる
k-2|  k-2            あとは各行、Aの示す最小値をどこか1マス書いておけば、残りは最小値以上最大値以下の何を入れても大丈夫

で、この数を数え上げる。

• $A$ のパターン数: $k^N-(k-1)^N$
  • $1～k$ を独立に並べる方法 $k^N$ から、$k$ を使わない方法 $(k-1)^N$ を引く
• $B$ のパターン数: $(N-k+1)^M$

これを $k=1,2,...,K$ について足し合わせればよい。

ただし、コーナーケースとして $N=1$ または $M=1$ の場合に注意。
例えば $N=1$ のとき、$B$ を決めたらマスへの書き込み方が一意に決まり、同時に $A_1$ も決まるので、自由度は $B$ の決め方しか無い。答えは $K^M$ となる。

Python3

E - Rvom and Rsrev

• 'a'と'b'のみからなる文字列 $S$ が与えられる
• 以下の操作を好きなだけ行って（行わなくてもよい）$S$ を辞書順最大化せよ
• 操作
  1. $S_i=S_j$（$i \lt j$）である $(i,j)$ を選ぶ
  2. $S_i,S_j$ を削除し、それに挟まれた文字列 $S[i+1 ... j-1]$ をひっくり返す
• 1つの入力につき $T$ ケース与えられる
• $1 \le T \le 2 \times 10^5$
• $1 \le (Tケースの|S|の合計) \le 2 \times 10^5$

aaabbbababba  この2文字に対して操作した場合
  v     v
aa babbb bba  操作した箇所を削除、その間をひっくり返す

aababbbbba
（本来は穴を詰めるが、どこに操作したかわかりやすくするため、穴は残して説明する）

辞書順最大化なので、ざっくり方針としては、'b'をなるべく多く先頭から並べた後、'a'も末尾に残せるなら最大数残さないといけない。

この問題は場合分けが多岐に渡るので、結果的には 「総当たりで正答を出すコードを書いて、16文字くらいなら高速に判定できるので全文字列についてチェックし、 自分の解答と正答が違ったらそのケースを観察」を繰り返すのが速かった。
でも本番中は切り替える決断が難しいのよね。

考察や発見を進めた順に書いていくと行ったり来たり非常に冗長になってしまうため、 最終的な結論ベースでまとめようかと思ったが、それならそれで公式解説でいいやとなってしまうな。
まぁあまり気にせず書こう。

場合分けの全体的な流れは以下になる。

Sの末尾が 'a'
|
`-  ①'b'を全て先頭に集め、'a'をなるべく多くその後に繋げる
      'bbb...bbaaa..aa' のような形にする

Sの末尾が 'b'
|
|-  'a'が偶数個
|    |
|    `-  ②'a'を全て消す
|          'bbb...bb' のような形にする
|
`-  'a'が奇数個
     |
     `-  以下の2つの大きい方
         |
         |- ③'a' を1個を残して全て消す
         |    'bbb...bbabbb..b' のような形にする
         |
         `- ④'b' に1回だけ操作して、
              'bbb...bbaaa..aa' のような形にする

ただし、④はさらに一癖ある。それは後述する。

全体に通じる指標として、辞書的順序にとって、先頭から'b'が続く個数を伸ばすのが最優先であることを念頭に置く。

以下、$S$ の'a'の個数を $c_a$ 個、'b'の個数を $c_b$ 個とする。
また、連続した'aaa…aa'を、1つの「'a'の領域」と呼ぶことにする。（'b'も同様）

以下のような操作を繰り返すことで、'b'を消さずに全て先頭に集められる。

                             (A) 末尾から連続する'a'の領域の左端 と
   aaabaaaaabaaaabbbaaa      (B) その他どこかの連続する'a'の領域の左端 を選ぶ
             v      v  
→ aaabaaaaab bbbaaa aa      (B)が(A)に統合される
                             ただし統合後の'a'の個数は(A)(B)の合計より2個だけ短くなる
       v         v
→ aaab bbb baaaa aa aa      繰り返す
   v         v
    b bbb baa aaa aa aa      bbbbbaaaaaaaaa となり、完成

必ずしも(A)で用いる領域を末尾に限定しなくても、 適当な中程の2つの領域を統合し、最後に末尾と統合してもいいんだけど、特に操作回数や'a'の個数は変わらない。
（1回の操作で結合される領域に着目すると、操作は高々2つの'a'の領域、2つの'b'の領域、それぞれを1つにすることしかできず、 最終形にするまでに結合すべき領域の個数は変わらないことから言える）

ここで注意すべきは、長さ1の'a'の領域がある場合。これを他と統合したら損になる。

よって、末尾以外の長さ1の領域は、2個ずつペアにしてあらかじめ消してしまうのが良い。
それでも1個残ったら、それは仕方ないので末尾と統合する。
（結合というより末尾の1個と打ち消してるといった方が近いけど、まぁ統一的に統合と呼ぶことにする）

これで作られる文字列が辞書順最大と言えるのかだが、 'b' は先頭から $c_b$ 個連続していて、当然、元からある個数以上は連続させられないのでこれが最大。 末尾に連なる'a'も、操作を領域の結合と見做すと必要な操作回数は決まってくるので、'b'を先頭に集める上ではこれ以上減らせない。
よってこれが最適と言える。

'a'に対して操作を繰り返して全て消すことで、'b'を $c_b$ 個並んだ状態に出来る。

末尾に'b'がある場合、1回は'b'に対して操作しないと動かしようが無いので、'b'を消さずにこの後ろに更に'a'を付けることは出来ない。

これも②と似た理論。残す'a'はなるべく後ろの方がよい。

操作後、末尾に3個以上の'b'が残ってしまうなら、'b'に1回操作してひっくり返した方が先頭からの'b'の連続数を稼げ、辞書順が大きくなる。

bbbbbbbabbbb      先頭からの連続: 7個
      v    v
bbbbbb bbba       先頭からの連続: 9個

そしてどうせ'b'に1回操作するなら、'a'もなるべく多く末尾に残したいので、④を試みる必要が生じる。

まぁ、細かな場合分けを見落とすのはイヤなので、③と④は両方やって比べればよい。

まず例外処理として、'aaaaabbbbb' のように 'a','b'の領域が各1個しか無い場合、 そもそも末尾を'a'にするのが不可能なので、④の場合は存在しない。③の結果が答えとなる。

基本的には、'b'に1回操作して末尾を'a'にした後、①と同様のことをすればよい。のだが。

「どの'a'を末尾に持っていくべきか」を気にする必要がある。

先頭に'a'の領域があった場合、そいつ単独で末尾に持っていくことは出来ない。
必ず、他の領域をまず末尾に持っていく必要がある。

つまり、

   aaaabbbbaaabb   こんなんなら問題なくて
          v    v
→ aaaabbb baaa    途中のaaaを末尾に持っていってから
   v        v
→  b bbbaaa aa    先頭を末尾に持っていけばいいのだが、


   aaabbbbbababb   こんなんの場合（他の途中領域が全て長さ1）
   aaabbbbb b bb   ×最初に長さ1の領域を消してしまっては先頭が動かせなくなるので
   
   aaabbbbbababb
          v    v
→ aaabbbb baba    ○最初に長さ1であろうと末尾に持っていって
   v          v
→  bab bbbbaa       先頭を末尾に持っていって
     v      v
→  b bbb bb a       余った長さ1の領域を処理する

という順にしないといけない。

そのため、「先頭以外の'a'の領域で長さ2以上のもの」の存在有無で場合分けする。

存在するのであれば、優先的に末尾に持っていくべきはそいつとなる。

存在しない場合、初手で長さ1の領域を末尾に持っていく必要がある。
（冒頭で例外処理した'aaaaabbbbb'のようなケースは除かれているので、先頭以外の'a'の領域は必ず存在する）

これで損が生じる場合というのが、長さ1の領域の個数が偶数個だった場合で、 本来は打ち消せる1ペアをばらして「末尾の'a'を作る用」と「余った1個」として2回結合に用いないといけなくなる。
（まぁもともとそうしないと辞書順最大を達成できないので“損”というのは変かもしれないが）

末尾に持っていく'a'が決まったら、後は①に帰着できる。

Python3