−目次

AtCoder Beginner Contest 167 C～F問題メモ

AtCoder Beginner Contest 167 C～F問題メモ

AtCoder Beginner Contest 167

C - Skill Up

問題

本が $N$ 冊あり、それぞれアルゴリズム $1～M$ について学べる
本 $i$ の価格は $C_i$ 円で、読むと各 $j=1～M$ についてアルゴリズム $j$ の理解度が $A_{i,j}$ 進む
今、全てのアルゴリズムの理解度は0
全てのアルゴリズムの理解度を $X$ 以上にするために必要な金額の最小値を求めよ
$1 \le N,M \le 12$

解法

$N$ が小さいので、どの本を買って、どの本を買わないか $2^N$ 通りを全て試せばよい。

1回試すのに $O(NM)$ かかるが、 $O(2^NNM)$ は最大値を当てはめても60万程度なので十分高速。

組み合わせを順に列挙していくのはbit演算を用いてもよいが、Pythonなら時間に多少余裕がある場合は、itertools.product() を使うと復元が楽になる。

itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.8.3rc1 ドキュメント

n = 4

for books in product([False, True], repeat=n):
    print(books)

# =>
# (False, False, False, False)
# (False, False, False, True)
# (False, False, True, False)
# (False, False, True, True)
# ...

さらに、NumPyを使うとこのようなbool値のlistによる配列アクセスはTrueの行のみを抽出する操作となるので、買う本のみの抽出を簡潔に書くことができる。

cost = np.array([10, 20, 30, 40])

cost[[True, False, True, False]]
# => [10 30]

cost[[True, False, True, False]].sum()
# => 40

        
          
          
              
              from itertools import product
import numpy as np
 
n, m, x = map(int, input().split())
cost = []
aaa = []
 
for _ in range(n):
    c, *a = map(int, input().split())
    cost.append(c)
    aaa.append(a)
 
cost = np.array(cost, dtype=np.int64)
aaa = np.array(aaa, dtype=np.int64)
 
ans = 10 ** 18
for books in product([True, False], repeat=n):
    books = list(books)
    if (aaa[books].sum(axis=0) >= x).all():
        ans = min(ans, cost[books].sum())
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

            

        
      

D - Teleporter

問題

$N$ 個の街がある
各街にはテレポーターが1個ずつあり、街 $i$ からは街 $A_i$ にテレポートする
街 $1$ から $K$ 回移動を繰り返すと、どの街に着くか答えよ
$2 \le N \le 2 \times 10^5$
$1 \le K \le 10^{18}$

解法

$K$ が大きすぎるのでシミュレーションは無理だが、街の数からして必ずどこかでループする。

1 → 6 → 4 → 5
         ↑   ↓
          2 ← 3

各街につき、街1からのテレポート回数を保存しておいて、既に回数が求まっている街に再び着いたとき、そこがループ起点となる。

ループを検出するとそこから「街1からループにたどり着くまでの移動回数 $s$ 」「ループの周期 $\lambda$ 」を計算できる。

もちろん、ループになる前に $K$ 回に達した場合はそれが答え。

それ以外では、 $(K-s) / \lambda = d あまり m$ とすると、ループは $d$ 周し、残り $m$ 回移動すればよいことになる。

つまり、街1から数えると、 $s+m$ 回移動した先が答え。これがどの街になるかは、最初にループを検出するまでに求まっている。

        
          
          
              
              import sys
 
n, k, *aaa = map(int, sys.stdin.buffer.read().split())
shortest = [-1] * n
v = 0
d = 0
while shortest[v] == -1:
    shortest[v] = d
    v = aaa[v] - 1
    d += 1
    if d == k:
        print(v + 1)
        exit()
 
first = shortest[v]
loop = d - first
remaining = (k - first) % loop
ans = shortest.index(remaining + first) + 1
print(ans)

            

        
      

ダブリングによる解法

こっちの方が計算量は若干かかるが、 $K$ がループ未満だったらとか細かなこと気にしないで短く書ける。

初期状態の $A$ は1回だけ移動した先だが、各 $i$ につき $B[i]=A[A[i]]$ とすることで、 $B$ は各街から2回移動した先を表す。

さらに $C[i]=B[B[i]]$ で4回先、さらに8回、16回、32回……と倍々の移動先を計算していける。

さて、 $K$ がたとえば49だったら、これを2のべき乗の和で表すと $49=1+16+32$ なので、1回移動→16回移動→32回移動、とすれば49回移動したことになる。

16回分の移動、32回分の移動というのは上記の方法で一気に計算できるので、都市1からの移動は実質3回しか行わないで済む。（32回分移動の配列を求めるのは必要だが）

$K \le 10^{18} \lt 2^{60}$ なので、最大値であっても2倍2倍を繰り返したら多くとも60回の移動の計算で済み、時間内に間に合う。

        
              import sys
 
n, k, *aaa = map(int, sys.stdin.buffer.read().split())
aaa = [0] + aaa
p = 1
while k:
    if k & 1:
        p = aaa[p]
    aaa = [aaa[a] for a in aaa]
    k >>= 1
print(p)

E - Colorful Blocks

問題

$N$ 個のボールを一列に並べ、それぞれを $M$ 種類の色のどれかで塗る
隣り合う2つのペア（ $N-1$ 個ある）のうち、2つの色が同じペアが $K$ 個以下になるような色の塗り方のパターン数を求めよ
$1 \le N,M \le 2 \times 10^5$

解法

色が同じペアが $k$ 個ちょうどのとき、どうなるか？

色が同じのを -- で結ぶ
N=8 k=3

o    o    o -- o -- o    o    o -- o

色の選び方
M   M-1   `-- M-1 --'   M-1   ` M-1 '    = M * (M-1)^4

「--」で結んだものは同じ色だから、まとめて1色を選べばよい。最初以外は、1つ前の色と被らない色を選べばよいので、 $M-1$ 通りから1色選ぶ。

色の選び方は、どのペアを同じにしようが $k$ が同じなら同じで、

o -- o    o -- o    o    o -- o    o

`- M -'   ` M-1 '  M-1   ` M-1 '  M-1    = M * (M-1)^4

なので、各 $k$ につき、以下の2つを掛け合わせたものが、その $k$ に対する色の塗り方のパターン数となる。

$N-1$ 箇所のペアから、色を同じにするペアの選び方: ${}_{N-1}C_{k}$ 通り
色の塗り方: $M \times (M-1)^{N-k-1}$ 通り

あとは、 $k=0～K$ までの結果を足し合わせればよい。

        
          
          
              
              def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs
 
 
n, m, k = map(int, input().split())
MOD = 998244353
facts, invs = prepare(n, MOD)
 
ans = 0
for s in range(k + 1):
    p = n - s
    ans = (ans + m * pow(m - 1, p - 1, MOD) * facts[n - 1] * invs[s] * invs[n - s - 1]) % MOD
print(ans)

            

        
      

F - Bracket Sequencing

問題

'(' と ')' からなる文字列が $N$ 個与えられる
好きな順に連結できる
上手く順番を決めて、全て連結した結果を正しい括弧列にすることが可能か判定せよ
- 正しい括弧列の定義は問題ページ参照

解法

正しい括弧列の判定は、定石としては '(' を +1、')' を -1として前から計算していったとき、以下の2つを満たすものである。

途中で1度も0未満にならない
最終結果が0

+1,-1するのは、「今、いくつの括弧を開いているか」と言い換えてもよい。

従って、各文字列につき、重要なのは以下の2つで、この他の情報は捨ててしまってよい。

一番最初を0として、
- $m$ : どこまで下がるか（途中で取り得る最小値）
- $t$ : 最終的な相対位置

              m   t
(()     ... ( 0,  1)
)(((    ... (-1,  2)
())))   ... (-3, -3)

とりあえずまずは、 $t$ の総和が0以外なら、'(' と ')' の数が釣り合ってないのでアウト。

以下、釣り合っているとする。

連結する順番を決めたとき、破綻するかどうかは、以下のように判定できる。

開いている括弧の数を保持する変数を $x$ とする。最初、 $x=0$
foreach 連結する文字列 $(m, t)$
- $x+m \lt 0$ なら、途中で0となるためアウト
- $x←x+t$
最後まで破綻しなければ可能

さて、ではどう順番を決めればよいか。

とりあえず、まずは $t$ が正のものを集めて、括弧を開けるだけ開いておいた方が安全な気がする。

証明は後でするとして、まずはそれで文字列を分類する。

すると、 $t$ が正の中では連結するたびにどんどん括弧は開いていくので、 $m$ が小さければ後回しにして、より括弧が開いた後に連結させた方がよい。

                  m   t
)))))((((((((   (-5,  3)  ← xが5以上の状態で連結する必要がある
()()()(         ( 0,  1)  ← xが0以上の状態なら連結して大丈夫

よって、 $m$ の降順にソートして連結させればよい。それでも無理なら無理である。

$t$ が負のものは、右から考えれば ')' で開き '(' で閉じることになるので、見る向きと意味合いを反転させれば正と同じように考えられる。

これで、貪欲に並び順を決めることができた。

$t$ が正のものだけを先に集めてくっつけて、負のものを後に集めるのが、正しいか確認する。この並べ方を「並び順1」とする。

一部の $t$ が負のものを先に持ってくれば本来可能なのに、並び順1では不可能と判定されてしまうケースがあったとする。この時の並べ方を「並び順2」とする。

$m$ の値は捨て置いて、 $t$ だけで $x$ の増減グラフを書くと、並び順1は必ず1つの山、2では一部に谷ができる。

並び順1                 並び順2
|      ／＼             |      
|    ／    ＼           |        ／＼
|  ／        ＼         |  ／＼／    ＼
|／            ＼       |／            ＼
+---------------------  +---+------+---------
                            |      |←並び順1との差分

さて、並び順1で破綻した文字列を、 $s_1=(m_1,t_1)$ とする。 $t_1$ は正とする。（負でも前後反転させれば一緒）

グラフ上では「／」として表されている中の1つである。

並び順1で破綻ということは、判定処理の途中で $x+m_1 \lt 0$ になった、つまり $s_1$ の処理までに $x$ を $m_1$ 以上にできなかったということ。

これを、並び順2で $m_1$ 以上にできるか？

途中で負なんて挟み込んでいるので、余計に無理である。

よって、矛盾するので、 $t$ が正のものを先に固めてしまって問題ない。

        
          
          
              
              def check(pt, brackets):
    brackets.sort(reverse=True)
    for m, t in brackets:
        if pt + m < 0:
            return -1
        pt += t
    return pt
 
 
n = int(input())
brackets_p = []
brackets_m = []
pt = 0
mt = 0
for _ in range(n):
    s = input()
    total = 0
    mini = 0
    for c in s:
        if c == '(':
            total += 1
        else:
            total -= 1
            mini = min(mini, total)
 
    if total >= 0:
        if mini == 0:
            pt += total
        else:
            brackets_p.append((mini, total))
    else:
        total, mini = -total, mini - total
        if mini == 0:
            mt += total
        else:
            brackets_m.append((mini, total))
 
pt = check(pt, brackets_p)
mt = check(mt, brackets_m)
 
if (pt == -1) or (mt == -1) or (pt != mt):
    print('No')
else:
    print('Yes')

            

        
      

Pythonでは 0 == False はTrueです。（check()の破綻したときの戻り値をFalseにして、0の時と区別できなくてWA出してた）

直前まで別の言語に触れてると、この辺って混乱することあるよね！（気付けよ）