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

AtCoder Regular Contest 118

A - Tax Included Price

• 消費税は $t$ パーセント
• 税抜き価格を $A$ とすると、税込み価格は $A \dfrac{100+t}{100}$ の小数点を切り捨てて計算される
• 税抜き価格が整数の場合、税込み価格としてあり得ない値のうち、小さい方から $N$ 番目の値を求めよ
• $1 \le t \le 50$
• $1 \le N \le 10^9$

税抜き価格 $A-1,A$ の時の税込み価格 $f(A-1),f(A)$ が連続した整数にならない時の $A$ を実験で挙げていくと、

3% : 34,67,100,134,167,200,...
4% : 25,50,75,100,125,150,175,200,...

と、100を $t$ で割った値をベースとして、100周期で並ぶことがわかる。

なので、答えの100より上の位は $\dfrac{N}{t}$ であり、あまりは実際に順番に調べても100個以内に見つかる。

Python3

B - Village of M People

• $N$ 人の人、$K$ 種類のレートがあり、レート $i$ の人は $A_i$ 人
• 世界がもし $M$ 人の村だったら、各レートは何人か求めよ
• もう少し具体的に言うと、以下の条件を満たす整数列 $B_1,B_2,...,B_K$ を求めよ
• 条件
  • $B_1+B_2+...+B_K=M$
  • その中で、$\max_i{|\dfrac{A_i}{N}-\dfrac{B_i}{M}|}$ が最小のもの
• $1 \le K \le 10^5$
• $1 \le N,M \le 10^9$

世界がもし100人の村だったら、現実で200人に1人くらいのマイナー属性を持った人は0になるので、 その村においてその属性が配慮されることはないのだなあ、なんて、その文章が流行ってた頃にちょっと思った。

$B_i$ が整数で無くていいなら指標 $|\dfrac{A_i}{N}-\dfrac{B_i}{M}|$ は厳密に0とできる。

そこから上か下に一番近い整数を $B_i$ とすれば、各指標は必ず1未満とできる。

上か下、というのがバラバラなのはややこしいので、とりあえず下に統一する。

つまり、仮として $B'_i=\dfrac{A_iM}{N}$（切り捨て）を求める。

そうすると合計を $M$ 人とするのに $M-\sum{B'_i}$ 人だけ余るので、それを適切な $B'_i$ に振り分ければよい。
つまり、答えは各 $i$ に対して全て $B_i = \{B'_i \ or \ B'_i+1 \}$ となる。

振り分け方は、貪欲に $\dfrac{A_i}{N}-\dfrac{B'_i}{M}$ が大きい順とすればよい。

B'i/M                     B'i+1/M
  |--①--|-------②--------|
       Ai/N

$B'_i$ のままだと誤差が①となるところ、$M-\sum{B'_i}$ 個だけ①から②に移す（損する場合でも）ので、①の大きい方から移した方がよい。

ただし誤差が怖いので、実際は $A_iM-B_iN$ で比較する。

Python3

C - Coprime Set

• 正整数 $N$ が与えられる
• 以下の条件を全て満たす長さ $N$ の数列 $A$ を構築せよ
• 条件
  • 全ての項は異なる
  • どの項も $10000$ 以下（$1 \le A_i \le 10000$）
  • どの2項を取っても最大公約数は1ではない（$gcd(A_i,A_j) \neq 1$）
  • $gcd(A_1,A_2,...,A_N)=1$
• $3 \le N \le 2500$

制約にもあるように、$N$ は最低3は必要。

    素因数
Ai  2 3 5    このようにすると
 6  o o      {6,10,15} が条件を満たす。
10  o   o
15    o o

$(6,10,15)$ の3数を $A$ に入れておけば、条件のうち「全体のGCDは1」は必ず満たされる。

残る条件「どの2項もGCDは1でない」を満たしつつ $A$ を拡張するには、 $gcd(6,x),gcd(10,x),gcd(15,x)$ が全て1にならない数だけを追加していけばよい。

すると追加できるのは $2,3,5$ のうち2つ以上の素因数を持つ数となり、つまり3数のどれかの倍数となる。
また、そのため、追加した数同士も必ず共通する素因数を持つことがわかる。

で、実際に構築すると10000までに2500以上の相異なる数が確保できるので、$(6,10,15)$ は必ず含めつつ、適当に $N$ 個抽出すればよい。

Python3

D - Hamiltonian Cycle

• 素数 $P$ と、$P$ 未満の正整数 $a,b$ が与えられる
• 次の条件を満たす長さ $P$ の数列 $A$ が存在するか判定し、存在するなら一例を示せ
• 条件
  • $A_1=A_P=1$
  • $A_2～A_{P-1}$ には、$2～P-1$ の数が1回ずつ出現する
  • 隣り合う2項は、$\mod{P}$ 上でどちらかがどちらかの $a$ 倍または $b$ 倍
• $2 \le P \lt 10^5$

素数modと累乗にまつわる性質として、以下がある。

• フェルマーの小定理
  • $a^{P-1} \equiv 1 \mod{P}$
• 原始根あたりの話題
  • $a^0,a^1,a^2,... \mod{P}$ が重複しないか順番に見ていって、最初に重複する値は必ず1
  • $a^k$ ではじめて1に戻るとすると、$k$ は必ず $P-1$ の約数

$a$ や $b$ が原始根なら単独で $A$ を構築できるが、まぁそんな上手くいくケースばかりではないだろう。

そうすると、仮に最初は $a$ の累乗で進めていくとして、 途中で1に戻ってしまうのを、$b$ で上手いことずらすんだろう、と想像がつく。

ところで、数列の各項は必ず $a^ib^j$ の形になる。$a^0b^0=1$ からスタートする。
$a^ib^j$ に隣り合えるのは $a^{i+1}b^j,a^{i-1}b^j,a^ib^{j+1},a^ib^{j-1}$ の4つが候補となる。

これって、グリッドを縦横に移動するのと似ている。

初期位置 $(0,0)$ に「1」を書き込み、その他には

• $(i+1,j)$ マスには、$(i,j)$ の $a$ 倍の数
• $(i,j+1)$ マスには、$(i,j)$ の $b$ 倍の数

となるように書き込む。

同じ数を踏まないように $(0,0)$ から上下左右に $P-1$ 回移動して「1」が書かれたどこかのマスに行ければ、その経路が答えとなる。

で、この構築方法と、同じ値を踏まないようにする方法がわからず。\\以下解説を見ての覚え書き。

• $a^1,a^2,...$ と調べていって、はじめて1に戻るのを $a^n$ とする
• 集合 $H=\{a^0,a^1,...,a^{n-1}\}$ とする
• $b^1,b^2,...$ と調べていって、はじめて $H$ に出てくる値と被るのを $b^m$ とする

するとグリッドに書かれた数字は、$n \times m$ の矩形がズレながらループする形で敷き詰められたようになっている。

(※ズレ幅は一例)

               (0,0)
             |-↓---------------------------------|
... a^5b^m-1 | 1     b   b^2   b^3  ...   b^m-1   | a^n-5  ...
... a^6b^m-1 | a    ab  ab^2  ab^3  ...  ab^m-1   | a^n-4  ...
             |                                    | ...
...          | ...                                |-------------
-------------|                                    | 1      ...
       b^m-1 |                                    | a
...          | a^n-1                 a^n-1b^m-1   | ...
             |------------------------------------|
... a^5b^m-1 | 1     b   b^2   b^3   ...  b^m-1   | a^n-5  ...

$n \times m$ がそもそも $P-1$ に満たなければ、 仮に矩形の中の値が全て異なっていたとしても、異なる値を $P-1$ 個用意できないので不可能。

そうで無い場合、値が全て異なっているかはひとまず置いて「$P-1$ 回の移動でちょうど1に戻れるルート」を考えると、

• $n$ は $P-1$ の約数

なので、$m$ から幅 $\dfrac{P-1}{n}$ を切り取って、$n \times \dfrac{P-1}{n}$ の長方形をくまなく回って $(0,0)$ の1に戻るか、または $(n,0)$ の1に抜けるルートを作ればよい。

この範囲の値が全て異なっていれば嬉しい。
実際にそれは証明できて、$nm \ge P-1$ であれば、必ず $nm=P-1$ となる。（公式解説 ◆$G_{a,b}$ の構造 参照）

なので、$n \times m$ の長方形をくまなく巡るルートを出力すればよい。

$n$ の偶奇で異なる。

偶数なら、牛耕式に抜ければよい。

１→→→↓
↓←←←←
→→→→↓
↓←←←←
１

奇数なら右下で終わってしまうので、1に戻れない。

ここで、$P \neq 2$ であれば、$P-1$ が偶数であることを利用できる。
つまり、縦が奇数なら、横幅は偶数である。

１→→→→↓
↑↓←↓←↓
↑↓↑↓↑↓
↑↓↑↓↑↓
↑←↑←↑←

$P=2$ の時は、$A=(1,1)$ で終わるため、例外処理しておけばよい。

Python3

E - Avoid Permutations

• 正整数 $N$ と、一部が欠損した $1～N$ の順列 $A_1,A_2,...,A_N$ が与えられる
• 以下の問題を考える
  • $N+2 \times N+2$ のグリッドを、左上 $(0,0)$ から右下 $(N+1,N+1)$ まで、右か下のみの移動でたどり着く
  • $1～N$ の（欠損してない）順列 $P$ がある
  • 各 $1 \le i \le N$ について、マス $(i,P_i)$ を通過してはいけない
  • 経路数を数え上げよ
• $A$ の欠損を、最終的に $1～N$ の順列となるように補う方法は、欠損個数を $t$ として $t!$ 通りある
• その全てに対して、それを $P$ としたときの問題の答えを求め、総和を $\mod{998244353}$ で求めよ
• $1 \le N \le 200$

DP。公式Editorialでは包除原理を使っているが、経路数を直接数え上げる方法でも解ける。（包除原理より面倒かも知れない）

• 黒マスの位置が決まっていない行・列を「曖昧な行・列」ということにする
• 黒マスの位置が決まっている行・列を「固定行・列」ということにする

以下のDPをベースとする。（このまま使うわけではなく、更新に必要な情報を後で考えていく）

• $DP[i][j]=$ 右と下のみの移動で $(0,0)$ から $(i,j)$ へたどり着く経路数
  • 順列に自由度がある場合は、全ての場合を足し合わせた数

たとえば、曖昧な行の個数が $t$ 個あったら順列の取り方は $t!$ 個あるので、スタート地点 $(0,0)$ にたどり着く(?)経路数は $t!$。
また、たとえば $(1,1)$ が確実に白マスの場合、$t!$ 通りの順列全てで2通りの経路で行けるので、経路数は $2(t!)$ となる。

遷移は、基本はよくある経路数え上げと同様、左上のマスから、上と左のDPの値を足していく。

ただし次のマスが黒マスになる確率が $p$ あったら、$DP[i][j] += DP[i-1][j] \times (1-p)$ というように、 場合によっては確率をかけて遷移する。

はじめ、以下でいけると思った。

• $DP[i][j][r][c]=$ マス $(i,j)$ へたどり着く経路数で、
  • $r=\{0,1\}$ : $i$ 行目が曖昧な行な場合、既に黒マスが置かれている/いない
  • $c=\{0,1\}$ : $j$ 列目が曖昧な列な場合、既に黒マスが置かれている/いない

ざっくりと、曖昧な行が全体で $t$ 個、$(i,j)$ より上に曖昧な行が $u$ 個あったら、 $(i,j)$ が黒マスになる確率は $\dfrac{t-u}{t}$ みたいに求められないかなー、みたいに考えた。

だが、これを適切に遷移させようとすると、列だけで無く行も併せて考えないといけない。
例えば曖昧な行に上側から遷移するとき、

      □←遷移元
□□□□←遷移先(曖昧な行)
`----'
ここに既に置かれてる確率、置かれてない確率がわからないと
遷移先の r=0,r=1 に適切に配分させられない。

そしてそれは $r,c$ だけではわからない。

$(i,j)$ の左上にある黒マスの個数の情報も必要になる。

    ,-- q ---,
            j
,-  □□□□□□...     p: (i,j)より上にある曖昧な行の数
p   □□□□□□...     q: (i,j)より左にある曖昧な列の数
|   □□□□□□...     k: p x q 内の曖昧な行・列に既に置かれた黒マス数
`- i□□□□◎□...
    □□□□□□...    （※固定行・列は省いて図示している）
    ...

もし $p \times q$ 内にたくさんの黒マスが既に置かれていたら、 $i$ 行目の◎より左に黒マスが置かれている可能性は低くなる。

逆にここがスカスカなら◎より左に黒マスが置かれる可能性は高くなるし、 さらには、ここで必ず置かないと後々、黒マスを $t$ 個置ききれなくなって破綻するかもしれない。

確率の計算には、$(i,j)$ を基準に、盤面を9個に分けて考える。

     ,---q--,,t-q,
           j
 ,-  ＡＡＡＢＣＣ   Ａにある黒マス数を k' とすると、
 p   ＡＡＡＢＣＣ   Ｄの中でまだ黒マス未配置の列数は(i) q-1-k'
 `- iＤＤＤＥＦＦ
 ,-  ＧＧＧＨＩＩ   またＢ+Ｃにある黒マス数はp-1-k'なので
t-p  ＧＧＧＨＩＩ   ＥＦの中でまだ黒マス未配置の列数は(ii) t-p-q+2-k'
 `-  ＧＧＧＨＩＩ   
                    Ｄに置かれる確率は (i) / (i)+(ii)

よって、左上矩形の黒マス数 $k$ の情報があれば、遷移先のマスの左や上に、 既に黒マスが置かれている確率が計算できることがわかった。

以下のDPをおこなう。結構ややこしい。

• $DP[i][j][k][r][c]=$
  • $(0,0)$ から $(i,j)$ に、
  • $(i,j)$ より左上の曖昧な行・列に置かれた黒マス数が $k$ 個で
  • $i$ 行目には既に $r=0/1$ 置かれていない/置かれていて、
  • $j$ 列目には既に $c=0/1$ 置かれていない/置かれている状態で
  • たどり着く経路数

ここまで次元数が多いと、配列の中身をprintするなどの即興的なデバッグには限界があるので、 どちらかというと計算式をベースに実装することが重要となる。

$k$ は上図では A+B+D+E の範囲だが、実際に遷移確率の計算に必要なのは A の情報だけなので、 これを直接持った方がよい気もする。 しかしそれだと更新時に $k$ を適切に保つためには、 $i$ 行目・$j$ 列目だけでなく $i-1$ 行目や $j-1$ 列目の 「曖昧な行か、固定行か」の情報も必要になってしまうため、$i$ 行目・$j$ 列目も含めることとした。

あとは、$(i,j)$ について「自身が曖昧な行か」「曖昧な列か」「曖昧な行の場合、既に上に置かれているか」「左に置かれているか」を場合分けして、遷移させればよい。

Python3