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

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

t, n = map(int, input().split())

# prev = 0
# for i in range(1, 1000):
#     tax = i + t * i // 100
#     if prev + 1 != tax:
#         print(i, prev + 1)
#     prev = tax

x = n // t
y = n - x * t
z = x * 100

prev = z + t * z // 100
z += 1
while y:
    cur = z + t * z // 100
    if prev + 1 != cur:
        y -= 1
    prev = cur
    z += 1

print(prev - 1)

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

k, n, m = map(int, input().split())
aaa = list(map(int, input().split()))

ccc = [a * m for a in aaa]
ddd = [c // n for c in ccc]
eee = [d * n for d in ddd]
fff = [(c - e, i) for i, c, e in zip(range(n), ccc, eee)]
fff.sort(reverse=True)

remain = m - sum(ddd)

for _, i in fff[:remain]:
    ddd[i] += 1

print(*ddd)

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

def extend(x, aaa):
    a = x
    while a <= 10000:
        aaa.add(a)
        a += x


n = int(input())

aaa = set()
extend(6, aaa)
extend(10, aaa)
extend(15, aaa)

aaa = sorted(aaa)
aaa[2], aaa[3] = aaa[3], aaa[2]

print(*aaa[:n])

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をおこなう。結構ややこしい。

$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

import os
import sys

import numpy as np


def solve(n, aaa):
    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions

    def get_mod_inv(n, MOD):
        facts, finvs = prepare_factorials(n, MOD)
        result = np.zeros(n + 1, np.int64)
        result[1] = 1
        for i in range(2, n + 1):
            result[i] = facts[i - 1] * finvs[i] % MOD
        return result

    MOD = 998244353

    mod_inv = get_mod_inv(n, MOD)

    row_ambiguity = np.zeros(n + 1, np.int32)
    row_ambiguity[1:] = np.cumsum(aaa == -1)
    col_ambiguity = np.ones(n + 1, np.int32)
    for a in aaa:
        if a >= 0:
            col_ambiguity[a] = 0
    col_ambiguity[0] = 0
    col_ambiguity = np.cumsum(col_ambiguity)
    ambiguous = row_ambiguity[-1]

    base = 1
    for i in range(2, ambiguous + 1):
        base = base * i % MOD

    dp_from = np.zeros((n + 1, ambiguous + 1, 4), np.int64)
    dp_from[:, 0, 0] = base
    dp_to = np.zeros_like(dp_from)
    # 2時限目: 自身の行・列を含め、自身より左上の矩形に置いた、ambiguousな黒マスの個数
    # 3次元目
    # row\col  0  1  その行/列に既に置かれたかどうか
    #   0      0  1
    #   1      2  3  fixedな行・列は0側

    ans = base

    for i in range(1, n + 1):
        dp_to[0, 0, 0] = base
        is_amb_row = aaa[i - 1] == -1
        row_amb = row_ambiguity[i - 1]
        for j in range(1, n + 1):
            if aaa[i - 1] == j:
                continue  # fixed block
            is_amb_col = col_ambiguity[j] - col_ambiguity[j - 1] == 1
            col_amb = col_ambiguity[j - 1]
            limit_amb = min(row_amb, col_amb)

            if is_amb_row:
                if is_amb_col:
                    # まだ置かれていない場合、そこに置かれる確率
                    iv_col = mod_inv[ambiguous - col_amb]
                    iv_row = mod_inv[ambiguous - row_amb]
                    for k in range(limit_amb + 2, -1, -1):
                        # 当列にまだ黒マスが置かれていない場合で、下移動したときに当行の左に黒マスが置かれていない確率
                        iv_not_d = (1 - (col_amb - k) * iv_row) % MOD
                        # 当行にまだ黒マスが置かれていない場合で、右移動したときに当列の上に黒マスが置かれていない確率
                        iv_not_r = (1 - (row_amb - k) * iv_col) % MOD
                        # 当行当列の両方にまだ黒マスが置かれていない前提で、当マスが黒マスにならない確率
                        iv_put = (1 - mod_inv[ambiguous - col_amb - row_amb + k]) % MOD
                        dp_to[j, k, 0] += (dp_from[j, k, 0] + dp_from[j, k, 2]) * iv_not_d % MOD * iv_put % MOD
                        dp_to[j, k, 0] += (dp_to[j - 1, k, 0] + dp_to[j - 1, k, 1]) * iv_not_r % MOD * iv_put % MOD

                        if k >= 1:
                            # 当列にまだ黒マスが置かれていない場合で、下移動したときに当行の左に黒マスが置かれている確率
                            iv_put_d = (col_amb - k + 1) * iv_row % MOD
                            # 当列に既に黒マスが置かれている場合で、下移動したときに当行の左に黒マスが置かれていない確率
                            iv_not_d = (1 - (col_amb - k + 1) * iv_row) % MOD
                            # 当行にまだ黒マスが置かれていない場合で、右移動したときに当行の上に黒マスが置かれている確率
                            iv_put_r = (row_amb - k + 1) * iv_col % MOD
                            # 当行に既に黒マスが置かれている場合で、右移動したときに当行の上に黒マスが置かれていない確率
                            iv_not_r = (1 - (row_amb - k + 1) * iv_col) % MOD

                            dp_to[j, k, 2] += (dp_from[j, k - 1, 0] + dp_from[j, k - 1, 2]) * iv_put_d % MOD
                            dp_to[j, k, 1] += (dp_to[j - 1, k - 1, 0] + dp_to[j - 1, k - 1, 1]) * iv_put_r % MOD
                            dp_to[j, k, 1] += (dp_from[j, k, 1] + dp_from[j, k, 3]) * iv_not_d % MOD
                            dp_to[j, k, 2] += (dp_to[j - 1, k, 2] + dp_to[j - 1, k, 3]) * iv_not_r % MOD

                        if k >= 2:
                            # 当列に既に黒マスが置かれている場合で、下移動したときに当行の左に黒マスが置かれている確率
                            iv_put_d = (col_amb - k + 2) * iv_row % MOD
                            # 当行に既に黒マスが置かれている場合で、右移動したときに当行の上に黒マスが置かれている確率
                            iv_put_r = (row_amb - k + 2) * iv_col % MOD
                            dp_to[j, k, 3] += (dp_from[j, k - 1, 1] + dp_from[j, k - 1, 3]) * iv_put_d % MOD
                            dp_to[j, k, 3] += (dp_to[j - 1, k - 1, 2] + dp_to[j - 1, k - 1, 3]) * iv_put_r % MOD

                    dp_to[j, :, :] %= MOD

                else:
                    iv = mod_inv[ambiguous - row_amb]
                    for k in range(limit_amb + 1, -1, -1):
                        # 下移動したときに当行の左に黒マスが置かれていない確率
                        iv_not = (1 - (col_amb - k) * iv) % MOD
                        dp_to[j, k, 0] += (dp_from[j, k, 0] + dp_from[j, k, 2]) * iv_not % MOD
                        if k >= 1:
                            # 下移動したときに当行の左に黒マスが置かれている確率
                            iv_put = (col_amb - k + 1) * iv % MOD
                            dp_to[j, k, 2] += (dp_from[j, k - 1, 0] + dp_from[j, k - 1, 2]) * iv_put % MOD
                    # 右移動
                    dp_to[j, :, 0] += dp_to[j - 1, :, 0] + dp_to[j - 1, :, 1]
                    dp_to[j, :, 2] += dp_to[j - 1, :, 2] + dp_to[j - 1, :, 3]
                    dp_to[j, :, :] %= MOD

            else:
                if is_amb_col:
                    # 下移動
                    dp_to[j, :, 0] += dp_from[j, :, 0] + dp_from[j, :, 2]
                    dp_to[j, :, 1] += dp_from[j, :, 1] + dp_from[j, :, 3]
                    iv = mod_inv[ambiguous - col_amb]
                    for k in range(limit_amb + 1, -1, -1):
                        # 右移動したときに当行の上に黒マスが置かれていない確率
                        iv_not = (1 - (row_amb - k) * iv) % MOD
                        dp_to[j, k, 0] += (dp_to[j - 1, k, 0] + dp_to[j - 1, k, 1]) * iv_not % MOD
                        if k >= 1:
                            # 右移動したときに当行の上に黒マスが置かれている確率
                            iv_put = (row_amb - k + 1) * iv % MOD
                            dp_to[j, k, 1] += (dp_to[j - 1, k - 1, 0] + dp_to[j - 1, k - 1, 1]) * iv_put % MOD
                    dp_to[j, :, :] %= MOD
                else:
                    dp_to[j, :, 0] += dp_from[j, :, 0] + dp_from[j, :, 2]
                    dp_to[j, :, 0] += dp_to[j - 1, :, 0] + dp_to[j - 1, :, 1]
                    dp_to[j, :, 0] %= MOD

        if is_amb_row:
            ans += dp_to[-1, row_amb + 1, 2] + dp_to[-1, row_amb + 1, 3]
        else:
            ans += dp_to[-1, row_amb, 0] + dp_to[-1, row_amb, 1]

        dp_from, dp_to = dp_to, dp_from
        dp_to.fill(0)

    ans %= MOD
    ans += base
    for j in range(1, n + 1):
        is_amb_col = col_ambiguity[j] - col_ambiguity[j - 1] == 1
        col_amb = col_ambiguity[j - 1]
        if is_amb_col:
            ans += dp_from[j, col_amb + 1, 1] + dp_from[j, col_amb + 1, 3]
        else:
            ans += dp_from[j, col_amb, 0] + dp_from[j, col_amb, 2]
    ans %= MOD

    return ans


SIGNATURE = '(i8,i8[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)
ans = solve(n, aaa)
print(ans)

目次

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

A - Tax Included Price

問題

解法

B - Village of M People

問題

解法

C - Coprime Set

問題

解法

D - Hamiltonian Cycle

問題

解法

グリッドグラフ

長方形巡りの旅

E - Avoid Permutations

問題

解法

基本方針

必要な情報

DP