AtCoder Beginner Contest 167 C~F問題メモ

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() を使うと復元が楽になる。

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出してた)

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

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2020/0510_abc167.txt · 最終更新: 2020/05/14 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0