AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

CODE FESTIVAL 2015 予選A D - 壊れた電車

問題原文

atcoder.jp

解法

 T 分で作業が終えることができる時、 T + 1 分でも作業を終えられる。
つまり単調性があるので、答えを二分探索できる。

次に二分探索内の判定を考える。
これは左詰め(あるいは右詰め)をするように貪欲的に点検していくのが最適。
ただし以下の点に注意する必要がある。

  1. 答えの上界は  N ではない。
    例えば  N = 100 X_1 = 50 とかだと折り返しが発生する。
    だいたい  1.5Nぐらいに設定しておけばいい。( 2N にしたけど)

  2. まず左に残っている点検し残りを処理 → 元の位置まで折り返し → 余った分右に進んで続きを点検、
    だけでなく、「(左に残っている点検し残りを処理できるように)右に進んで続きを点検 → 元の位置まで折り返し → 左に残っている点検し残りを処理」 がある。

2にたいそうやられてしまった。

実装

N, M = map(int, input().split())
X = [int(input()) for _ in range(M)] + [N + 1]  # 番兵
 
# にぶたん: T分で点検作業が終わるか?
ok, ng = 2 * 10 ** 9, -1
while abs(ok - ng) > 1:
    T = (ok + ng) // 2
    done = 0
    for i in range(M):
        left_remain = X[i] - done - 1
        if left_remain > T:
            break
 
        done = X[i] + max(max(0, T - 2 * left_remain), (T - left_remain) // 2)
        done = min(done, X[i + 1] - 1)
 
    if done >= N:
        ok = T
    else:
        ng = T
 
print(ok)

感想

2にたいそうやられてしまった。。。
左詰め貪欲と右詰め貪欲をやるだけだと、  N = 10,  X_1=2, X_2=9 のようなパターンで5にならないんですよね。。。 (両方端まで塗って折り返すのが最適のため)

Donutsプロコンチャレンジ2015 B - Tokyo 7th シスターズ

問題原文

atcoder.jp

解法

なんかすごそう。
入力がとてもとてもめんどくさそう。

少し落ち着いて見ると、   {}_{16} C_9 × M ≒ 6 × 10^{5} 程度なので全部試せることがわかる。

実装

from itertools import combinations
N, M = map(int, input().split())
A = list(map(int, input().split()))
B, P = [], []
for i in range(M):
    row = list(map(int, input().split()))
    B.append(row[0])
    P.append(set([r - 1 for r in row[2:]]))

ans = 0
for select in combinations(range(N), 9):
    select = set(list(select))
    tmp_ans = 0
    tmp_ans += sum([A[s] for s in select])
    for b, p in zip(B, P):
        if len(p & select) >= 3:
            tmp_ans += b
    ans = max(ans, tmp_ans)

print(ans)

感想

試験管水が解けなくて逃げてきたのだけどこれも水diffゥ!!

Code Formula 2014 予選B C - 仲良し文字列

問題原文

atcoder.jp

解法

3回のswapで影響範囲があるのは最大6文字まで。それより大きいと3回では足りない。
よって  A_i B_i が異なるindexを列挙しておいて、実際に3回のswapを全探索する。

 A の中に同じ文字が複数あれば、それらをswapすることで回数を稼げることに注目。
具体的にはそのような場合、 ちょうど3回のswap でなく 3回以下のswap と条件が変わる。

実装

こういうのは再帰で書くのが楽なのではないでしょうか。

from itertools import combinations
A = list(input())
B = list(input())

diff = []
dupulicate_char_index = -1
appeared = set()
for i, (a, b) in enumerate(zip(A, B)):
    if a != b:
        diff.append(i)
    if a in appeared:
        dupulicate_char_index = i
    appeared.add(a)
if dupulicate_char_index != -1:
    diff += [dupulicate_char_index] * (6 - len(diff))

# 達成不可能
if len(diff) > 6:
    print('NO')
    exit()


def check(a, change_cnt):
    if (dupulicate_char_index != -1 or change_cnt == 3) and (a == B):
        print('YES')
        exit()


def dfs(a, depth):
    if depth == 3:
        return
    for i, j in combinations(diff, 2):
        a[i], a[j] = a[j], a[i]
        check(a, depth + 1)
        dfs(a, depth + 1)
        a[i], a[j] = a[j], a[i]

dfs(A, 0)
print('NO')

感想

結構難しかった。。。

東京海上日動2020 C - Lamps

問題原文

atcoder.jp

解法

1回分の操作はいもす法を使うことで  O(N) でできる。 これを  K 回行うので、  O(NK)、さてどう高速化するか。。。となるけど、実は愚直にやっても  logN 回程度の操作で  N, N, ... N に収束する。
ので、実際には  O(NlogN) で答えを求められる。

 A = 0, 0, ... 0 のケースを手計算してたら気がついた。
一番操作回数が多くなるのは  A = 0, 0, ... 0 で、両端が一番  N になるまで時間がかかる、という事実をもとにちゃんと観察すればまだはやく気づけたかも。(だいたい倍々になっていく)

実装

from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))


def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    imos = list(accumulate(imos))
    return imos[:-1]


for k in range(min(50, K)):
    A = calc_imos(A)
print(*A, sep=' ')

感想

えーん、もう少し早く解きたかった。

ARC011 C - ダブレット

問題原文

atcoder.jp

解法

グラフ構築 + BFS + 経路復元、という問題。

グラフ構築

「1文字変えたら相手の文字列になれる」ような  s1,  s2 を見つけ、その間に辺を張ってグラフをつくる。
単語の文字数は MAX30文字らしいので、愚直にやっても大丈夫。

BFS

辺のコストが全て1なので、単純なBFSで最短経路長が求められる。
復元できるように「どこから来たか」の情報を格納しながらやる。

経路復元

BFSのときにやった「どこから来たか」の情報を逆に辿りながら復元する。

sample2みたいな最初からゴールしてるやつがあるので注意(だるいので別で分けた)

実装

from collections import deque
start, end = input().split()
N = int(input())
words = [start] + [input() for _ in range(N)] + [end]
G = [[] for _ in range(N + 2)]


# だるいので別処理
if start == end:
    print(0)
    print(start)
    print(end)
    exit()


# グラフ構築
for i, word1 in enumerate(words):
    for j, word2 in enumerate(words):
        diff = 0
        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                diff += 1
            if diff > 1:
                break
        else:
            if diff == 1:
                G[i].append(j)


# 復元できるようにしながらBFS
que = deque([0])
froms = [None] * (N + 2)
froms[0] = -1

while que:
    n = que.pop()
    for to in G[n]:
        if froms[to] is not None:
            continue
        que.appendleft(to)
        froms[to] = n


# 答えを計算
if froms[-1] is None:
    print(-1)
else:
    ans_num = 0
    ans_words = []
    marker = N + 1
    while marker != -1:
        ans_num += 1
        ans_words.append(words[marker])
        marker = froms[marker]
    print(ans_num - 2)
    print(*ans_words[::-1], sep="\n")

感想

PASTででそう(雑)

ARC040 C - Z塗り

問題原文

atcoder.jp

解法

上から & 右から優先でみていけばいいです!
右上残しても結局後から塗らなきゃならないからね!おわり!

実装

N = int(input())
S = [list(input()) for _ in range(N)]
S.append(['o'] * N)  # 番兵

ans = 0
for r in range(N):
  for c in reversed(range(N)):
    if S[r][c] == '.':
      S[r] = ['o'] * (c + 1) + S[r][c + 1:]
      S[r + 1] = S[r + 1][:c] + ['o'] * (N - c)
      ans += 1
      break

print(ans)

感想

PAST初級で出そう!おわり!

ABC015 D - 高橋くんの苦悩

問題原文

atcoder.jp

解法

ナップサック問題発展版。「個数」という制約が追加されている。
やり方はいろいろあると思うんですが、  O(WN^{2}) がなんか嫌な予感がしたので、「価値に対する最小の重さ」っぽくやりました。
詳しくは実装がわかりやすいかと。

実装

ちょっとサボっている。
PyPy3で700ms、142MBぐらい。
直前の配列だけ持つようにすれば想定解でもMLEしないのかな。しらんけど。

W = int(input())
N, K = map(int, input().split())
Items = [list(map(int, input().split())) for _ in range(N)]
MAX_V = 50 * 100
INF = 10 ** 9

# dp[i][k][v] := i番目まで見てk個選んだ時に価値の総和がvになるために必要な最小幅合計
dp = [[[INF] * (MAX_V + 1) for j in range(K + 1)] for i in range(N + 1)]
dp[0][0][0] = 0
for i, (a, b) in enumerate(Items):
  for k in range(K + 1):
    for v in range(MAX_V + 1):
      dp[i + 1][k][v] = min(dp[i + 1][k][v], dp[i][k][v])
      if v + b <= MAX_V and k + 1 <= K:
        dp[i + 1][k + 1][v + b] = min(dp[i + 1][k + 1][v + b], dp[i][k][v] + a)

ans = 0
for k in range(K + 1):
  for v in range(MAX_V + 1):
    if dp[-1][k][v] <= W:
      ans = max(ans, v)
print(ans)

感想

サクッと解けたけど、数ヶ月前は手も足も出なかっただろうな。。。
dpは成長を感じられてうれしい。