2020-05-20

ABC165 C - Many Requirements

競プロ

問題原文

解法

$N$ と $M$ の制約が小さいことに注目する。

全パターン試すのが楽そうだけど、条件を満たすような数列はどれぐらいあるかを考える。
例えばバラバラの数字 $k$ 個を適当に並べてそれが単調増加になっている確率は $\frac{1}{k!}$ 。
この事実を考えると最大ケースでもめちゃくちゃ通り数が削られることがわかる。

$Q$ の制約も小さいので、これら全てについて愚直にスコアを計算しても余裕で間に合う。

けんちょんさんの考え方に勉強させていただきました。ありがとうございます。 drken1215.hatenablog.com

実装

再帰でかける。
.append() -> dfs() -> .pop() とけんちょんさんの記事ではやっていて、なるほどと思った。
（↓ はそれではないです）

from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]
ans = 0

def calc(arr):
    score = 0
    for a, b, c, d in X:
        if arr[b - 1] - arr[a - 1] == c:
            score += d
    return score


def dfs(arr):
    global ans
    if len(arr) == N:
        ans = max(ans, calc(arr))

    elif len(arr) == 0:
        for nx in range(1, M + 1):
            dfs(arr + [nx])

    else:
        for nx in range(arr[-1], M + 1):
            dfs(arr + [nx])


dfs([])
print(ans)

ところでpythonだと itertools.combinations_with_replacement がめちゃくちゃ便利。
Twitterで教えてもらった（ありがとうございます）

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

中でソートしてる分ちょっと遅いはずだけど、まぁ全然大丈夫。

from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
for pattern in combinations_with_replacement(range(1, M + 1), N):
    tmp_ans = 0
    pattern = list(pattern)
    for a, b, c, d in X:
        if pattern[b - 1] - pattern[a - 1] == c:
            tmp_ans += d
    ans = max(ans, tmp_ans)

print(ans)

感想

たくさん知見を得られた良い問題でした。
正答率が思ったより低くてへぇ〜ってなった（数学系の問題の方が強い人多いのかな？）

2020-05-04

第二回 PAST K - 括弧

競プロ

問題原文

atcoder.jp

問題要旨

(, ) からなる $S$ を対応の取れた括弧列にすることを考える。
まず、以下の操作を0回以上行う。

$i$ 文字目の ( と ) を反転させる。コストとして $C_i$ かかる。

次に、以下の操作を0回以上行う。

$i$ 文字目を削除する。コストとして $D_i$ かかる。

$S$ を対応の取れた括弧列にするための最小コストを求めよ。

$1 \leq N \leq 3000$

解法

atcoder.jp

↑をやっておくと、 ((の個数) - ()の個数) での状態の同一視が思い浮かぶ。
あとは、

$dp[i\rbrack[x\rbrack :=$ $i$ 文字目までみて ((の個数) - ()の個数) が $x$ のような状態にするための最小コスト

として、丁寧にdpテーブルを埋めていけば終わり。
各文字について、操作１と２の両方をやることは明らかに損なので、同時に好きな操作を選べると考えて大丈夫。

魔力発電をやってなくても「対応の取れた括弧列かどうか」の判定ロジックを考えると、

それまでの ( の個数が ) の個数以上。
最終的な ( の個数と ) の個数が同じ。

にたどり着けて、そこからテーブル定義が見えそう、な気がする。

atcoder.jp

をやっておくと、ここまではわかるかも。

実装

丁寧に。

N = int(input())
S = input()
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
# dp[i][j]:= i文字目まで見たときに「(の数 」- 「)の数」をjにするための最小コスト
dp = [[float('inf')] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i, s in enumerate(S):
    if s == '(':
        for j in range(N + 1):
            cost0 = dp[i + 1][j]
            cost1 = float('inf')  # そのまま
            cost2 = float('inf')  # 変換
            cost3 = float('inf')  # 削除
 
            if j - 1 >= 0:
                cost1 = dp[i][j - 1]
 
            if j + 1 < N:
                cost2 = dp[i][j + 1] + C[i]
 
            cost3 = dp[i][j] + D[i]
 
            dp[i + 1][j] = min(cost0, cost1, cost2, cost3)
 
    elif s == ')':
        for j in range(N + 1):
            cost0 = dp[i + 1][j]
            cost1 = float('inf')  # そのまま
            cost2 = float('inf')  # 変換
            cost3 = float('inf')  # 削除
 
            if j + 1 < N:
                cost1 = dp[i][j + 1]
 
            if j - 1 >= 0:
                cost2 = dp[i][j - 1] + C[i]
 
            cost3 = dp[i][j] + D[i]
 
            dp[i + 1][j] = min(cost0, cost1, cost2, cost3)
 
 
print(dp[-1][0])

感想

これ瞬殺できたのは確実にJOI精進のおかげだなぁと思います。
でも今だと緑diffつきそうでこわいね。

2020-05-04

第二回 PAST J - 文字列解析

競プロ

問題原文

atcoder.jp

問題要旨

英子文字と (, ) からなる「括弧の対応が取れているような」文字列 $S$ が与えられる。
また、 $rev(a)$ を文字列 $a$ を反転した文字列とする。
以下の操作を可能中桐繰り返し行った時の、最終的な $S$ を求めよ。

(, ) を含まない $S$ の部分文字列 $a$ を、 $a + rev(a)$ で置きかえる。
$1 \leq |S| \leq 1000$
最終的な $S$ の長さは1000以下。

解法

逆ポーランド記法を勉強したことがあれば、スタックに積んでいくのが思い浮かびます。
あるいは、

atcoder.jp

を解いておくとパッと思い浮かびます。

経験が無い場合には、
1. 内側の括弧から処理が入る。
2. ) がきた時に処理が入る。
3. ) がきた時には、 ( が出るまできたみちを戻りたい。

という気持ちになると解けるのかなぁという感じです。

実装

S = input()
stack = []
 
for s in S:
    if s != ')':
        stack.append(s)
    else:
        r = ''
        while stack[-1] != '(':
            r += stack.pop()
        stack.pop()
        stack.extend(list(r[::-1]))
        stack.extend(list(r))
 
print(''.join(stack))

感想

スタックうまく使えると自尊心が満たされた気がします。

2020-05-04

第二回PAST I - トーナメント

競プロ

問題原文

atcoder.jp

問題要旨

$2^{N}$ 人でトーナメントをおこなう。 $i$ 番目の人の強さは $A_i$ で、これらは相異なる。
トーナメントでは隣の人と戦って、より強い方が勝ち残る。これを最後の１人になるまで行う。
各人について何回戦うかを求めよ。

$1 \leq N \leq 16$

解法

シミュレーションをします。終わりです。（？？？）
半分の半分の。。。となっていくので、計算量は余裕です。

実装

優勝者がもう一度闘争を求め出してしまったで特別に処理をしました。

N = int(input())
A = list(map(int, input().split()))
A = [(a, i) for i, a in enumerate(A)]
 
ans = {}
for n in range(N):
    winners = []
    for i in range(2 ** (N - n - 1)):
        xa, xi = A[2 * i]
        ya, yi = A[2 * i + 1]
        if xa > ya:
            ans[yi] = n + 1
            winners.append((xa, xi))
        else:
            ans[xi] = n + 1
            winners.append((ya, yi))
 
    winners.sort(key=lambda x: x[1])
    A = winners[:]
 
winner = A[0][1]
for n in range(2 ** N):
    if n == winner:
        print(N)
    else:
        print(ans[n])

感想

I <<<<<<<<<<< H だと思うんです。
いや別に必ずしも難易度順というわけではないんですが、 Hを一旦パスしてめっちゃ身構えて I をみたので世界が好きになりました。

2020-05-04

第二回 PAST H - 1-9 Grid

競プロ

問題原文

atcoder.jp

問題要旨

S, G がひとつずつ、それと 1 ~ 9 で構成される $H × W$ のグリッドが与えられる。上下左右への移動を繰り返して、S から G へ向かう時、 1 ~ 9 のマスを 1, 2 ... 9 の順番に踏んでいるようなものの最小の移動回数を求めよ。
そのような経路が存在しない場合は -1 とせよ。
ただし、同じマスを複数回通って良く, S, G も途中で通っても良い。 1 の次 2 を踏む必要はなくて、 1 5678 2 みたいな移動でももちろんOK。ただしこの場合には途中に通った 5678 は条件を満たした扱いにならない。

$1 \leq H, W \leq 50$

解法

とりあえず、 S を 0, G を 10 にエンコードした。

そのあと、なんとか状態の同一視をやりたいな〜という気分になって、 $dp[h\rbrack[w\rbrack[k\rbrack :=$ マス $(h, w)$ にいて、最後にチェックした条件を満たすような数字が $k$ であるような状態になるための最小移動回数
というdpテーブルを定義してみた。で、なんとなくできそうなのでこの方針でいくことに。

更新順がわかんないので、メモ化再帰でなんとなく G から埋めて行きました。

実装

結構苦戦した。
結局次の数字のマスにしか遷移してないので、dpの $k$ の部分は持たなくてよかったね多分。

import sys
sys.setrecursionlimit(10 ** 9)
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
P = {i: [] for i in range(11)}
 
# S: 0, G: 10にエンコード。ついでにGのindex取得。あと出現位置記録
Gh, Gw = None, None
for h in range(H):
    for w in range(W):
        if G[h][w] == 'S':
            G[h][w] = 0
        if G[h][w] == 'G':
            Gh, Gw = h, w
            G[h][w] = 10
 
        P[int(G[h][w])].append((h, w))
 
for h in range(H):
    G[h] = list(map(int, G[h]))
 
for v in P.values():
    if not v:
        print(-1)
        exit()
 
# dp[h][w][k] := マス(h, w)にいて、最後にチェックした（1~9の並びにカウントした）マスがkであるようなものの最小移動回数
dp = [[[float('inf')] * 11 for w in range(W)] for h in range(H)]
 
 
def dfs(nh, nw, k):
    if k == 0:
        return 0
 
    if dp[nh][nw][k] != float('inf'):
        return dp[nh][nw][k]
 
    ret = float('inf')
    for ph, pw in P[k - 1]:
        ret = min(ret, dfs(ph, pw, k - 1) + abs(nh - ph) + abs(nw - pw))
 
    dp[nh][nw][k] = ret
    return ret
 
 
print(dfs(Gh, Gw, 10))

感想

これを解いて上級を確定させた。
普通にこの後出てくる問題より難しかった気がするぞ。。。

2020-05-04

第二回 PAST G - ストリング・クエリ

競プロ

問題原文

atcoder.jp

問題要旨

文字列 $S$ に対して、 $Q$ 回のクエリを実行せよ。
最初 $S$ は空文字列である。クエリには以下の２種類ある。
1. $S$ の末尾に英子文字 $C_i$ を $X_i$ つ追加する。
2. $S$ の先頭から $D_i$ 文字削除する。この操作で、 a, b, ... z がそれぞれ何文字削除されたかを求め、それぞれの削除個数の二乗の和を出力する。

$1 \leq |S| \leq 10^{5}$
$1 \leq X_i \leq 10^{5}$
$1 \leq D_i \leq 10^{5}$

解法

愚直にやってはダメなので、うまく状態を管理できないかを考える。
(文字種, 何文字続くか) という形で $S$ をもてば追加も削除も楽に管理できる。

実装

削除の形はABCとかでたまにみますね。
先頭削除は deque を使うべし。

from collections import deque
Q = int(input())
S = deque([])
 
for q in range(Q):
    query = input().split()
    if query[0] == '1':
        c, x = query[1], int(query[2])
        S.append([c, x])
 
    elif query[0] == '2':
        d = int(query[1])
        cnt = {chr(ord('a') + i): 0 for i in range(26)}
        d = int(query[1])
 
        while d and S:
            c, x = S[0]
            if x <= d:
                cnt[c] += x
                d -= x
                S.popleft()
            else:
                S[0][1] -= d
                cnt[c] += d
                d = 0
 
        ans = sum([v ** 2 for v in cnt.values()])
        print(ans)

感想

緑下diffのABC-D感があるなぁと思いました。

2020-05-02

JOI難易度７展覧会

競プロ

問題原文

atcoder.jp

問題要旨

大きさ、価値がそれぞれ $S_i$ , $V_i$ であるような絵が $N$ 枚と、大きさが $C_j$ であるような額縁が $M$ 個ある。
各絵はそれよりも大きなサイズの額縁にしか入れることはできない。
また、絵を額縁に入れて飾る時、額縁の大きさについても絵の価値についても広義単調増加になっている必要がある。
最大で何枚の絵を入れられるか。

$1 \leq N, M \leq 10^{5}$

解法

「こういうのは現時点で入れられる絵を管理するんですよ〜」っていいながら考えてたら普通にハマった。（方向性自体は多分だけど正しいと信じている）

まず、額縁は必ず大きい順に並ぶのでソートしておいて問題なし。
で、ここから良さげなパターンが２つ思い浮かぶ。

額縁が大きい方から見て行って、その額縁に入る絵のうち、最も価値の高いものを入れる。
額縁が小さい方から見て行って、その額縁に入る絵のうち、最も価値の低いものを入れる。

ただ2は、大きさが極小だけど価値が極大みたいな絵があった時に採用してしまうのでダメだとわかる。
（逆に１は「さっきは入らなかったけど、今は額縁に入って、それでいてこれまで入れたどんな絵よりも価値が高い」という状況が生まれない。一番大きな額縁に入れられる絵の集合は、二番目に大きな額縁に入れられる絵の集合を包含している。）

じゃぁ１か〜となって、絵の大きさについてソートしておいて、「今の額縁に入るものがまだあるか？」をセグ木とかで判定しようとしたけどTLEしてかなしいねになる。

で、発想をちょっと変えて価値に目線をおくと、「価値が大きいものから入れられるかチャレンジをして、入れられるなら入れてしまう」で損をしないこと、結局絵を入れる順番は同じなことががわかる。

これでようやくAC。

実装

def main():
    import sys
    my_input = sys.stdin.readline
    N, M = map(int, my_input().split())
    arts = [list(map(int, my_input().split())) for _ in range(N)]
    frames = [int(my_input()) for _ in range(M)]
    INF = float('inf')
 
    arts.sort(key=lambda x: [x[1], x[0]], reverse=True)
    frames.sort(reverse=True)
 
    ans = 0
    cursor = 0
    for frame in frames:
        while (cursor < N) and (arts[cursor][0] > frame):
            cursor += 1
 
        if cursor < N:
            ans += 1
            cursor += 1
 
    print(ans)
 
 
if __name__ == "__main__":
    main()

感想

はい典型〜じゃないんですよね。
証明力がないので説明があってるか不安になる。。。