税抜き価格 $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個以内に見つかる。
世界がもし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$ で比較する。
制約にもあるように、$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$ 個抽出すればよい。
素数modと累乗にまつわる性質として、以下がある。
$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」を書き込み、その他には
となるように書き込む。
同じ数を踏まないように $(0,0)$ から上下左右に $P-1$ 回移動して「1」が書かれたどこかのマスに行ければ、その経路が答えとなる。
で、この構築方法と、同じ値を踏まないようにする方法がわからず。\\以下解説を見ての覚え書き。
するとグリッドに書かれた数字は、$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に戻れるルート」を考えると、
なので、$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)$ で終わるため、例外処理しておけばよい。
DP。公式Editorialでは包除原理を使っているが、経路数を直接数え上げる方法でも解ける。（包除原理より面倒かも知れない）
以下のDPをベースとする。（このまま使うわけではなく、更新に必要な情報を後で考えていく）
たとえば、曖昧な行の個数が $t$ 個あったら順列の取り方は $t!$ 個あるので、スタート地点 $(0,0)$ にたどり着く(?)経路数は $t!$。
また、たとえば $(1,1)$ が確実に白マスの場合、$t!$ 通りの順列全てで2通りの経路で行けるので、経路数は $2(t!)$ となる。
遷移は、基本はよくある経路数え上げと同様、左上のマスから、上と左のDPの値を足していく。
ただし次のマスが黒マスになる確率が $p$ あったら、$DP[i][j] += DP[i-1][j] \times (1-p)$ というように、 場合によっては確率をかけて遷移する。
はじめ、以下でいけると思った。
ざっくりと、曖昧な行が全体で $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をおこなう。結構ややこしい。
ここまで次元数が多いと、配列の中身をprintするなどの即興的なデバッグには限界があるので、 どちらかというと計算式をベースに実装することが重要となる。
$k$ は上図では A+B+D+E の範囲だが、実際に遷移確率の計算に必要なのは A の情報だけなので、 これを直接持った方がよい気もする。 しかしそれだと更新時に $k$ を適切に保つためには、 $i$ 行目・$j$ 列目だけでなく $i-1$ 行目や $j-1$ 列目の 「曖昧な行か、固定行か」の情報も必要になってしまうため、$i$ 行目・$j$ 列目も含めることとした。
あとは、$(i,j)$ について「自身が曖昧な行か」「曖昧な列か」「曖昧な行の場合、既に上に置かれているか」「左に置かれているか」を場合分けして、遷移させればよい。