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,\ldots$ と決め打ったら、$B \times C$ の上限は $\dfrac{K}{1}, \dfrac{K}{2}, \dfrac{K}{3},\ldots$ となり、次に $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,\ldots,N$ に対し、$A_i$ は $i$ 行目のマスに書かれた整数の最小値
    • $j=1,\ldots,M$ に対し、$B_j$ は $j$ 列目のマスに書かれた整数の最大値
  • 数列 $(A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,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,\ldots,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 \ldots 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'を消さずに全て先頭に集められる。

   abababbbabaaaabbbaaa
                             (A) 末尾から連続する'a'の領域の左端 と
→ abababbbab[a]aaabbb[a]aa  (B) その他どこかの連続する'a'の領域の左端 を選ぶ

→ abababbbab bbbaaa aa      (B)が(A)に結合される
                             ただし結合後の'a'の個数は(A)(B)の合計より2個だけ短くなる

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

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

よって、末尾以外の長さ1の領域は、2個ずつペアにしてあらかじめ消してしまうのが良い。
それでも1個残ったら、それは仕方ないので操作を行って末尾に持っていく(というか、末尾の1個と打ち消す)。

'b' は当然ながら先頭から $c_b$ 個以上は連続させられないし、 末尾に連なる'a'も、「1回の操作で全体から2ずつ減る」「必要な操作回数は決まっている」ので、これが最適となる。

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

末尾に'b'がある場合、1回は'b'に対して操作しないと動かしようが無いので、 'b'を先頭から $c_b$ 個並んだ状態にするには、'a'を全て消すしかない。

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

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

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

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

末尾に残るのが1個や2個なら③の方がよいが、まぁ細かな場合分けを見落とすのはイヤなので、両方やって比べればよい。

まず例外処理として、'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の領域を末尾に持っていく必要がある。
(冒頭で例外処理したケースは除かれているので、長さ1の領域も存在しない、ということはない。必ず存在する)

これで損が生じる場合というのが、長さ1の領域の個数が偶数個だった場合で、 本来は打ち消せる1ペアをばらして「末尾の'a'を作る用」と「余った1個」として結合に用いないといけなくなる。

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

Python3

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2021/0221_arc113.txt · 最終更新: 2021/02/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0