AtCoder Regular Contest 102 C～F問題メモ

AtCoder Regular Contest 102

解説放送: AtCoder Regular Contest 102/ Beginner Contest 108 解説放送 - YouTube

C - Triangular Relationship

• 整数 $N,K$ が与えられる
• $1 \le a,b,c \le N$ なる3つの整数を考える
• $a+b,b+c,c+a$ のいずれも $K$ の倍数となる $(a,b,c)$ の組の個数を求めよ
  • $a,b,c$ は互いに区別する

• $a+b=l \times K$
• $b+c=m \times K$
• $c+a=n \times K$

とした時、$(a+b)+(b+c)-(c+a)=2b=(l+m-n)\times K$ なので、$2b$ は $K$ の倍数となる。同様のことが $2a,2c$ にも言える。

$a,b,c$ は全て $K$ の倍数となる。

$N$ 以下の整数で $K$ の倍数が $k$ 個とすると、$a,b,c$ のそれぞれがその中のどれになってもよいので、$k^3$ 通りが答えとなる。

$a,b,c$ は「全て $K$ の倍数」か「全て $K$ で割ると $K/2$ 余る数」となる。

それぞれの個数が $k,l$ の時、$k^3+l^3$ が答えとなる。

D - All Your Paths are Different Lengths

• 整数 $L$ が与えられる
• 頂点数 $N \le 20$、辺数 $M \le 60$ の有向重み付きグラフを作る
  • 頂点には1から $N$ までの番号が付く
  • 辺は必ず小さい番号から大きい番号に張る
  • 多重辺があってもよい
• 頂点1から $N$ までの経路の数は $L$ 通りになるようにする
• 各経路の距離は、全て異なり 0～$(L-1)$ の $L$ 通りとなるようにする
• $1 \le L \le 10^6$

L=5
        ,------0-----,
①--0--②--1--③--0--④--0--⑤
  `-----3-----' `-----1-----'

• 1-2-4-5: 0
• 1-2-3-4-5: 1
• 1-2-3-5: 2
• 1-3-4-5: 3
• 1-3-5: 4

5通りの経路があり、各距離が0～4となっている。

たとえば、ある頂点 $v$ までの経路が3通りあり、各経路の距離が $\{2,5,9\}$ だった時、$v$ から重み4の辺を通った先の頂点 $w$ は、$\{6,9,13\}$ となる。さらに多重辺として重み5の辺もあれば、経路は6通りに増え、$\{6,7,9,10,13,14\}$ となる。

{2,5,9}          {6,9,13}
   v ----- 4 ----- w

{2,5,9}          {6,9,13, 7,10,14}
   v ----- 4 ----- w
    `----- 5 -----'

異なる辺を通った時の数値が被らないように各辺の重みを設定する必要がある。すると、飛び飛びよりは、なるべく $v$ に至る経路の距離は連続してる状態を保った方がやりやすそう。

{0,1,2}          {0,1,2, 3,4,5, 6,7,8}
   v ----- 0 ----- w
   |------ 3 ------|
   `------ 6 ------'

$n$ 進数のように考えると、下記のようにすると $n$ の冪乗数通りの経路までは距離が被らずに構築できると分かる。（辺数の制約もあるが）

①--- 0 ----②---- 0 ----③---- 0 -----④- ... (N)
 |--- 1 ---|  |--- n ---|  |--- n^2 --|  |-     -|
 |--- 2 ---|  |---2n ---|  |--2(n^2)--|  |-     -|
 ...     ...  ...     ...  ...      ...  ...   ...
 `-- n-1 --'  `-(n-1)n--'  `(n-1)(n^2)'  `-     -'

経路のパターン数
 1         n          n^2         n^3      n^(N-1)
各経路の距離
(0)     0～n-1     0～n^2-1    0～n^3-1  0～n^(N-1)-1

ここで制約を見ると頂点数20以下なので、$n^{19}$ 通りの経路が構築できる。

試しに $n=2$ とすると、$2^{19}=524288$。$L=10^6$（制約の最大値）の時、$10^6$ を超えない2の冪乗数が19、つまり必要な頂点数20で丁度合致するので、2進数で考えてよさそう。

必要な辺数も38本なので、残りの経路の調整分を追加することを考えても、余裕がある。

これで $L$ を超えない2の冪乗数までは構築できた。残りの経路をどうするか。

途中の頂点 $k$ から(N)に直接辺を張ると、新たに $2^{(k-1)}$ 通りの経路が追加される。

                       ,------------------,
①--- 0 ---②--- 0 ---③--- 0 ---④- ... (N)
 `--- 1 ---'`--- 2 ---'`--- 4 ---'`-     -'

$L$ を2進数で表現し、最上位を除いて下から $d$ 桁目が'1'であれば、頂点 $d$ から(N)に辺を張ればよい。

辺追加前のグラフにおける経路のパターン数が $p$ で、各距離が 0～$(p-1)$ を実現できているとすると、追加する辺の重みを $p$ とすることで、辺追加後は経路のパターン数が $p+2^{(k-1)}$ となる。これを繰り返せばよい。

L=13
13を超えない2の冪乗数が8なので、8通りの経路を持つグラフを構築
  ,--0--,  ,--0--,  ,--0--,
①---1---②---2---③---4---④

L=13 → 2進数で1101 → 最上位を除いた101に着目
下から3桁目が'1' → ③から④に辺を追加する
  ,--0--,  ,--0--,  ,--0--,
①---1---②---2---③---4---④
                    `--8--'
重みは、今の経路数が8で、0～7の距離が埋まっているので、8とする
これにより、経路数は12、0～11の距離が埋まる

下から1桁目が'1' → ①から④に辺を追加する
  ,--0--,  ,--0--,  ,--0--,
①---1---②---2---③---4---④
 |                  `--8--'
 `-----------12-----------'
重みは、今の経路数が12で、0～11の距離が埋まっているので、12とする
これにより、経路数は13、0～12の距離が埋まる

解説放送の方法。

$L=2$ の時、グラフは以下の形で実現できる。

①-- 0 --②
  `- 1 -'

$n=2$ から始めて「$n$ に1を足す」「$n$ に2をかける」のいずれかを繰り返して、$L$ にする最短操作手順を求める。

各操作に対応して、グラフを更新していく。

「$n$ に1を足す」場合、①から(N)（現時点の最大番号の頂点）に、重み $n$ の辺を追加する

①-- 0 --②  →  ①-- 0 --②
  `- 1 -'          |- 1 -|
                   `- 2 -'

「$n$ に2をかける」場合、各辺の重みを2倍し、さらに頂点を追加して重み0,1の2辺を張る

①-- 0 --②  →  ①-- 0 --②-- 0 --③
  `- 1 -'          `- 2 -'  `- 1 -'

$L=13$ での挙動を見て見る。操作手順は2ー(+1)→3ー(x2)→6ー(x2)→12ー(+1)→13である。

L=2
①-- 0 --②
  `- 1 -'
L=3 (+1)
①-- 0 --②
  `- 1 -'
  `- 2 -'
L=6 (x2)
①-- 0 --②-- 0 --③
  `- 2 -'  `- 1 -'
  `- 4 -'
L=12 (x2)
①-- 0 --②-- 0 --③-- 0 --④
  `- 4 -'  `- 2 -'  `- 1 -'
  `- 8 -'
L=13 (+1)
①-- 0 --②-- 0 --③-- 0 --④
  `- 4 -'  `- 2 -'  `- 1 -'
  `- 8 -'                 |
  `----------12-----------'

このように、

• 自明な $n$ で答えを求める
• 「$n$ に1を足す」「$n$ に2をかける」の手順を求める
• 各操作に対応した処理を行う

という発想は解法1より汎用的で、当てはめられる問題がたまにあるらしい。

E - Stop. Otherwise...

• 整数 $K,N$ が与えられる
• $K$ 面サイコロを $N$ 個振る
  • $K$ 面サイコロには、1～$K$ の整数が書かれている
  • サイコロは互いに区別しない
• 各 $i=2,3,...,2K$ に対し、以下の値を $\mod{998244353}$ で求めよ
  • どの異なる2つのサイコロの出目の合計も $i$ にはならない、出目の組の場合の数
• $1 \le K \le 2000$
• $2 \le N \le 2000$

$K=6$ 面サイコロを $N=3$ 個振る。
$i=2,3,...,12$ について答えを求める。

たとえば $i=5$ の時、(1,4)または(2,3)の組があってはいけない。
それを含まない (1,3,6) や (2,2,2) のような出目の組はOK。
(1,4,5) や (2,2,3) のような出目の組はNGとなる。

サイコロは互いに区別しないことに注意すると、44組が該当する。

1面サイコロとは一体……

公式解説の解法はこの問題に特化したスマートな方法だが、より汎用的な方法として、包除原理を使って解ける。

各 $i$ ごとに、「合計が $i$ となる組を含む出目の場合の数」を求めて全体 ${}_KH_N$ から引けば、答えである「合計が $i$ となる組を含まない出目の場合の数」が求まる。サイコロは区別しないので全体の場合の数は重複組み合わせで求める。

「合計が $i$ となる組を含む出目の場合の数」を求める際に包除原理を用いる。

最近のARCでも何度か出ているが、数え上げ問題で、ダブリを解消するのに有効な手法。

たとえば $i=5$ の時、合計が5となる組は(1,4)と(2,3)のいずれか。（$K$ が4以上の場合）

これらが含まれる場合の数を数えるには、「$N$ 個中2個を(1,4)や(2,3)に固定して、残りを自由に決める」という方法を用いるとよい。

$K=4,N=5$ を例に取ると、「2個を(1,4)または(2,3)に固定」で2通り、残りの3個を決めるのに ${}_4H_3=20$ 通り、掛け合わせて40通り…となりそうだが、実際には間違いとなる。

それは、(1,4)も(2,3)も両方含む場合を重複して数えているから。これが4通りあるため、36通りが正しい答えとなる。

(1,4)を含む   (2,3)を含む
     /~~~~~~x~~~~~~\
    /      / \      \
   |   16 | 4 | 16   |
    \      \ /      /
     \______x______/

$i=5$ のように該当する組が2通りの場合は「(1組を固定する場合の合計)-(2組をともに固定する場合)」でよかったが、これが $i=10$ で(1,9),(2,8),(3,7),(4,6),(5,5)の5つとかとなると、3組固定する場合、4組固定する場合…を一体どう考えればいいか？

包除原理によると、以下のように考えてよい。シンプル。

• (1組を固定)-(2組を固定)+(3組を固定)-(4組を固定)+…
• $\displaystyle =\sum_{q=1}(-1)^{(q-1)}(q組を固定する場合の数)$

並び順は区別しないので、ペアの小さい方を数える。上限は $\frac{i}{2}$(切り捨て)。下限は、$i \ge K+2$ の場合は $i-K$、それ以外は1となる。

このペア数を $p$ とする。

まず、$q$ ペアの選び方で ${}_pC_q$ 通り。

残りの $N-2q$ 個のサイコロの出目は、${}_KH_{N-2q}$ 通り。

これを掛け合わせたのが「合計が $i$ になるペアが $q$ 組入った出目の場合の数(重複あり)」となる。

なお、ペアの中に(5,5)のように同じ数字のものが存在するかどうかは気にしなくてよい。(4,6)など異なる数字のペアと同様に扱ってよい。ペアを使うと決めた時点で2個固定されるし、使わないと決めたのに自由に決められる残りの方に入っていたとしても、後で除去される。

全ての取り得る $q$ について上記の重複含みの場合の数を求め、包除原理に従って $q$ が奇数なら足し、偶数なら引いた合計が、重複無しの「合計が $i$ になるペアを含む場合の数」となる。

これを全体から引いた結果を出力すればよい。

$q$ の範囲は基本的に $1～p$ だが、$N$ が小さい場合はそもそも $p$ 個も作れないので $1～\frac{N}{2}$ となることに注意する。

以上を考えると、場合の数に影響するのは $K,N$ の固定値を除けば $p$ のみであり（$q$ は $p$ に依存）、$i$ が異なってもそこから算出される $p$ が同じであれば場合の数は等しいと分かる。

一度計算した $p$ については再計算を省くことが出来る。

どのような $i$ に対する $p$ が等しくなるかを考えると、以下のようになる。

K=6のときの2つのサイコロの合計
     1  2  3  4  5  6
  +------------------
 1|  2  3  4  5  6  7
 2|     4  5  6  7  8
 3|        6  7  8  9
 4|           8  9 10
 5|             10 11
 6|                12  （サイコロは区別しないので、入れ替えて被るものは空欄）

合計が同じになる出目は、斜めに現れる（この個数が p）
→2と12, 3と11, 4と10, ...は p が同じになる＝答えが同じになる
→計算するのは2～7まででよい
（更に、2と3、4と5...も同じになるので、実質的な計算は1つ飛ばしでよい）

F - Revenge of BBuBBBlesort!

• バブルソートとは、隣接する2数が $p_i \gt p_{i+1}$ ならひっくり返すことを繰り返して、ソートする
• これを踏まえて、以下の操作を考える
  • 隣接する3数が $p_{i-1} \gt p_i \gt p_{i+1}$ の箇所があれば、ひっくり返す
• 要素数 $N$ の、$1～N$ を並べ替えた数列 $p_1,p_2,...,p_N$ が与えられる
• 操作を繰り返して、$1,2,...,N$ にソートできるか判定せよ
• $3 \le N \le 3 \times 10^5$

まず適当にやってみよう。

5  4  3  2  1
  ↓
3  4  5  2  1
        ↓
3  4  1  2  5

あれ、もうこれ以上操作できなくなってしまった。結構、操作の制約がきついっぽい。

操作を逆順に考える。1,2,3,…と並んだ数列から、昇順に並ぶ3数を逆順にすることを繰り返して、与えられた数列にできればよい。

1  2  3  4  5
3  2  1  4  5
3  2  5  4  1

ここで、隣り合う2数への操作に着目するとある性質が見えてくるそうだ。

もし $i-1$ や $i+1$ で既に操作済みの $i$ があったとする。どちらでも対称なので、$i-1$ の方で最後に操作を行った前提とする。

     i-3  i-2  i-1   i   i+1  i+2
...   3    4    5    6    7    8  ...
                ↓
...   3    6    5    4    7    8  ...

この状態で、$i$（今のところ5,4,7）に対して操作を行えるか？

$i-1$ での操作により $5>4$ となっているので、このままでは無理。行うには5か4のどちらかを別の数字に入れ替えなければならない。

4の方を入れ替えることができるのは、$i-1$ か、$i+1$ を中心とした操作のみ。しかし、$i-1$ で入れ替えたら入れ替えた後の状態について堂々巡りになる。また、$i+1$ で入れ替えるのは、前提に反する。よって4の方は変えられない。

じゃあ5だが、これを変えられるのは $i-2$ か $i$ を中心とした操作のみ。$i$ はしようとしてできないという話なので、$i-2$ を中心として操作するしか無い。

しかし、これも、$i-1$ での操作により $6>5$ となっているので、このままではできない。6か5のどちらかを入れ替えなければならない。

おさらいすると、今、$i$ で操作するために $i-2$ での操作が必要で、その準備のための操作を考えている。 よって $i, i-2$ を中心とした操作は行えないので、5は入れ替えられない。 なので、6を入れ替えるしか無い。

6を入れ替えられるのは $i-3$ と $i-1$ だが、$i-1$ もこの時点では昇順に並んでいないので、$i-3$ で操作して6をより小さい数字にするしか無い。

すると、$i-3$ で操作を行った後、$i-2$ で操作を行えないと、$i$ では操作をできないということまで分かった。

では、そういう操作は実際に行えるのか？ つまり、$i-3$ で操作を行った後、$i-2$ で操作できるのか？

これは、当初の命題「$i-1$ で操作を行った後、$i$ で操作できるか？」を、2個左にずらした形となる。 よって、これに対する答えは「$i-5$ で操作を行った後、$i-4$ で操作をすることができれば、できる」となる。

これをずっと繰り返していくと、いつかは左端に達し、それ以上操作を行えなくなるタイミングが来る。 つまり、連鎖的に必要条件が否定され、「$i-1$ で操作を行った後、$i$ で操作はできない」となる。

同じことが、$i+1$ に対しても言える。よって、ある数を中心として操作したら、隣接する数に対する操作はできない。

ここから派生して、ある数を移動させるには隣接要素を中心に操作するしか無いので、 「ある数を中心として操作したら、その数は初期状態から移動できず、最終的にも $i=p_i$」ということが言える。

連続する2数に対して操作できないことから、移動の一方通行性も言うことができる。

ある数を交換して右（左）に移動させた。これを後で左（右）に移動させることはできるか？

...  4   A   B  ...    4 < A < B
        ↓
...  B   A   4  ...

4を右に移動する操作を行った。これを後で左に移動させられるか？

操作後、左隣の要素Aは当然4より大きい。さらに一度中心とした要素は初期より変わらないため、Aはこのままである。

4を左に移動させるにはもう一度Aを中心として操作するしか無いが、Aの右隣が4である限り、昇順の条件を満たさないのでできない。

よって、一度右（左）に移動させた要素は、後から左（右）に移動させることはできない。

一度でも移動させた要素は、元の位置に戻すことはできない。

上記を踏まえて考えると、数列は、以下のような区間に分割できる。

＊: そこを中心として操作した
ー: そこを中心としては操作してない
| : 区間の区切り

i  1  2  3  4  5  6  7   8  9 10   ...
   -  *  -  *  -  *  - | -  *  - | -  *  -  *  - | - | - | -  *  -  *  -  *  -

この区間をまたいでは、数字は行き来できない。つまり、区間 $[l,r]$ の数字は、$l,l+1,...,r$ で構成されていなければならない。

また、“*” のある区間の“-“は必ず $i \ne p_i$ であり、”*” や、単独の“-“は必ず $i=p_i$ である。

よって、区間の区切りは「$i \ne p_i$ である要素が連続」「$i=p_i$ である要素が連続」している箇所となる。

さらに、ある1区間の $i \ne p_i$ の要素のみに着目する。 移動の一方通行性から、$i$ と $p_i$ の大小関係で「初期より左に動いた」「初期より右に動いた」に分類できる。

ここで、同じ方向に動いた要素同士の順番は、入れ替えることができない。（入れ替えた時点でその2要素は異なる方向に動いたということであり、一方通行性に反する）

以上の条件を守っていれば、区間の中で端に位置する要素から順に左（右）に寄せていけば、好きなように並べ替えられそうである。

以下のアルゴリズムで判別できる。

1. $i=p_i$ か $i \ne p_i$ の連続で、区間を分割する
2. 各区間が、$[l,r]$ なら $l,l+1,...,r$ で構成されているか確認する
3. 各区間で移動した要素を左移動と右移動に分け、その中では大小関係が変化していないことを確認する

何というか、解説を読んで追うことはできても、「着目点に気付く」「それが全てであると確信する」ハードルがとても高い。