2020-05-24

Indeedなう（予選B） C - 木

競プロ

問題原文

解法

「その時点で選べる頂点のうち、番号が最小のものを選ぶ」のが最適。

問題はそのような頂点を高速に取得することだけど、これは優先度付きキューを使うと簡単に実現できる。

実装

import heapq
N = int(input())
T = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)

ans = []
hq = [0]
visited = set()

while hq:
    n = heapq.heappop(hq)
    ans.append(n)
    visited.add(n)
    for to in T[n]:
        if to in visited:
            continue
        heapq.heappush(hq, to)

print(*[a + 1 for a in ans], sep=' ')

感想

推定水diffらしい。
今だと下手すると茶diffがつきかねないなぁという印象。

2020-05-24

天下一コン2014 予選B B - エターナルスタティックファイナル

競プロ

問題原文

atcoder.jp

解法

dp。

$dp[i\rbrack := S[0: i\rbrack$ を構築する通り数

としてdpテーブルを順に埋めていく。

実装

なんだろう、拾う方が気持ちイメージが楽な気がします。
今 $i$ までを見ていて、最後に $t$ を使ってできるかな〜？というきもち

N = int(input())
S = input()
lenS = len(S)
T = [input() for _ in range(N)]
MOD = 10 ** 9 + 7

dp = [0] * (lenS + 1)
dp[0] = 1

for i in range(lenS + 1):
    for t in T:
        if i - len(t) < 0:
            continue
        if S[i - len(t):i] == t:
            dp[i] += dp[i - len(t)]
            dp[i] %= MOD

print(dp[-1] % MOD)

感想

いつものノリで「 $i$ 番目までみたときに〜」でなんとなく書いたら、 $S =$ aaaa で a と aa がある時に、 aa a を取れなくて悲しくなった。
$S[0: i\rbrack$ を見る時に、全ての $t$ について $S[0: i - 1\rbrack$ までの計算を終わらせておく必要がありそう。

2020-05-23

ABC167 E - Colorful Blocks

競プロ

問題原文

atcoder.jp

解法

ポイントはまとめて全パターン考えないようにすることだと思う。

まず、「隣り合う色が同じようなものがない」パターンを考えてみる。
これは、例えば一番左は $M$ 色使えて、次からは直前に使った色でない $M- 1$ 色を使えるので、 $M × (M - 1)^{(N - 1)}$ 通りとなる。

この色がバラバラな状態からイメージを膨らませて、「隣り合う色が同じような場所を作る」とは、「２〜 $N$ 番目のブロックのうち、左隣と色が違うものを左隣の色にする」 ことだと考える。

次に、隣り合うブロックの組で色が異なるものが、 $K$ 以下でなく、 $k$ 個として固定して考える。
とすると、通り数は、

(最初の１つで $M$ 通り) × ( $N - 1$ 個の色を揃えられるポイントのうちどの $k$ 個を使うか) × (それぞれのブロックを何色で塗るか)

で求められることになる。

「 $N - 1$ 個の色を揃えられるポイントのうちどの $k$ 個を使うか」については、 ${}_{N - 1} C_k$ で求められる。
「それぞれのブロックを何色で塗るか」については、 $k$ 個分自由に選べる場所が減っているので、 $(M - 1)^{(N - 1 - k)}$ になる。

上記の計算を全ての $k$ に対してやればおしまい！

実装

逆元コンビネーションを使う。

N, M, K = map(int, input().split())
MOD = 998244353

ans = 0
for k in range(K + 1):
    ans += M * nCr(N - 1, k) * pow(M - 1, N - 1 - k, MOD) % MOD
    ans %= MOD

print(ans % MOD)

感想

$k$ の結果を $k - 1$ から計算しようとしてダメだった（する必要なかった）
あと 101 みたいなのがあった時に、真ん中を 1 にしたら同じ色の箇所が２箇所増えるじゃんと思っていた。
これは、先にどの部分を同じ色にするかを決めておいて、後から適切な色を割り当てていく とイメージすれば回避できたはず。

上式はぱっと浮かんだのに、余計なことを考えてしまってハマってしまった。。。数え上げ苦手ぇ

2020-05-23

ABC167 D - Teleporter

競プロ

問題原文

atcoder.jp

解法

$K$ の制約がとても大きいため、実際に $K$ 回の移動を試すわけにはいかない。

全ての町について、必ずどこかに町に移動できるのでいずれどこかのループをぐるぐる回ることになる。

ループは $N$ 回以内に必ず現れるので、どこがループするかを計算しておく。
これがあれば移動結果を高速に求められる。

ループに入る前に $K$ 回の移動を終えてしまう場合に少し注意する。

類題というか、ほぼ同じ問題が旧ABCに出ている。 atcoder.jp

実装

stackに積んでおいて、ループ始点が出るまで pop() とすると楽かなぁ。。。と思った。

N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))

stack = [0]
visited = {0}

# どこからループが始まるかを探す
now = 0
while A[now] not in visited:
    now = A[now]
    stack.append(now)
    visited.add(now)
roop_start = A[now]

# 実際にどこがループしているのかを探す
roop = []
while stack[-1] != roop_start:
    roop.append(stack.pop())
roop.append(roop_start)
roop = roop[::-1]
roop_size = len(roop)

# ループに入るまで移動を試す。K回移動してしまっても終わり。
now = 0
while now != roop_start and K:
    now = A[now]
    K -= 1

# ループの情報を元に答えを計算する。
if K == 0:
    print(now + 1)
else:
    print(roop[K % roop_size] + 1)

感想

diff700かぁ。。。みんな実装力あるなぁ。。。

2020-05-21

ABC166 F - Three Variables Game

競プロ

問題原文

atcoder.jp

解法

全部の数がある程度大きければ適当にやっていけばできそうなことがわかる。

ということでできるパターンのギリギリ、あるいは死ぬパターンを考える。

0 0 0 の場合

問答無用で死ぬ。

1 0 0 の場合

0 0 の部分を操作されると死ぬ。

1 1 0 の場合

1 1 を指定されると 0 0 がどこかに生まれ、その次に生まれた 0 0 を指定されると死ぬ

1 1 1 の場合

適当に少ない方を助けるように動いてけばよさそう。
例えば１回操作すると 2 1 0 とかになるけど、 1 1 がないので１つ前のパターンみたいに慎重になる必要はない。
なんとなく 0 1 2 の３種類のことだけ考えれば良さそうなことがわかる。

0 0 0 と 1 0 0 はどうしようもない時はどうしようもないので、 1 1 0 のパターンをいかに Yesにするかを考える。
2 0 0 を作って１手空くと 1 1 0, 1 0 1 のどちらかには戻れるので、死ぬとしたら直後のターンであることがわかる。
よって次のターンのことを考えて死なないように選ぶのが最適。

実装

頑張ってまとめてみたかったんです。。。

N, A, B, C = map(int, input().split())
S = [input() for _ in range(N)]

A, B, C = min(A, 2), min(B, 2), min(C, 2)
X = [0, A, B, C]  # 1-indexecの方が楽そう
F = {1: 'A', 2: 'B', 3: 'C'}

ans = []
for k, s in enumerate(S):
    if s == 'AB':
        i, j = 1, 2
    elif s == 'BC':
        i, j = 2, 3
    elif s == 'AC':
        i, j = 1, 3

    if X[i] > X[j]:
        X[i] -= 1
        X[j] += 1
        ans.append(j)

    elif X[i] < X[j]:
        X[i] += 1
        X[j] -= 1
        ans.append(i)

    else:
        if (X[i] == X[j] == 1) and (k < N - 1):
            if ((S[k + 1][0] == F[i]) and (S[k + 1][1] == F[i ^ j])) or ((S[k + 1][0] == F[i ^ j]) and (S[k + 1][1] == F[i])):
                X[i] += 1
                X[j] -= 1
                ans.append(i)
            else:
                X[j] += 1
                X[i] -= 1
                ans.append(j)
        else:
            X[i] -= 1
            X[j] += 1
            ans.append(j)

    if any([x < 0 for x in X]):
        print('No')
        exit()

print('Yes')
for a in ans:
    print(F[a])

感想

1 ^ 2 = 3, 1 ^ 3 = 2, 2 ^ 3 = 1、どこかで役に立つかもしれない。

2020-05-21

ABC166 E - This Message Will Self-Destruct in 5s

競プロ

問題原文

atcoder.jp

解法

条件を整理すると、

$abs(i - j) = A_i + A_j$

が探したいものだとわかる。

とりあえず $j ＞ i$ として絶対値を消すと、

$j - i = A_i + A_j$

になった。

こういうのは $i$ と $j$ を別々に考えるとよくて、式変形をすると

$i + A_i = j - A_j$

が得られる。

これで左辺と右辺が独立に前計算できるようになった。
あとは全ての $i$ についてペアになれる $j$ がいくつあるかを数えればいい。
i = j で条件を満たすようなものはないので考えなくて大丈夫。

実装

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

P = [i + a for i, a in enumerate(A, start=1)]
Q = [j - a for j, a in enumerate(A, start=1)]

ans = 0
QC = Counter(Q)
for p in P:
    ans += QC[p]

print(ans)

感想

あれ、なんか強くなってる気がする。

2020-05-20

ABC165 D - Floor Function

競プロ

問題原文

atcoder.jp

解法

$N ＜ B$ ならば右側が必ず０になるので、 $x$ には取りうる一番大きい数である $N$ を入れるのが最適。
そうでない時、 左側は $A$ をかけてる効果を最大に活かしたくて、右側は値が変わるギリギリに押さえ込みたい 気持ちになるので、 $B - 1$ を入れるのが良さそうということがわかる。
一応 $n(B - 1)$ を何個か試して答えが変わらないことを確認しておわり！

実装

A, B, N = map(int, input().split())
 
def calc(x):
    return ((A * x) // B) - A * (x // B)
 
if N < B:
    print(calc(N))
else:
    print(calc(B - 1))

感想

Cの倍以上解かれていてみんな数式につえ〜って思ってました