ABC176 D - Wizard in Maze
久しぶりにコンテスト中にDまで解けた！嬉しい～～！
問題概要
グリッドグラフが与えられる．スタートのマスからゴールのマスまで移動したい．移動する操作は2種類ある．移動Aは現在のマスから上下左右に1マス移動できて，移動Bは現在のマスを中心とした，5×5の範囲内のマスに移動できる1．
移動Bが必要な最小の回数を求めよ．ただし，スタートからゴールにどうやっても到達できなければ-1を出力せよ．
解法
2回BFSをする．
1回目はグリッドグラフ上で行う．移動Aのみで移動できる範囲で，各マスをグループ分けする． 各グループを一つの頂点とみなしたグラフを作成し，移動Bで移動できる頂点間に辺を張る． 作成したグラフ上で，2回目のBFSをし，スタートマスの頂点からゴールマスの頂点への最短距離を求める．
たとえば入力例4だと次のような感じ．
1回目のBFSでグループ分け．
各マスから，どのグループにワープできるか走査．壁でないマスはすべて調べる．
あとはグラフを作成する．このグラフ上でBFSすると求める最短距離がわかる．
コード
def main():
from collections import deque
H, W = (int(i) for i in input().split())
Ch, Cw = (int(i)-1 for i in input().split())
Dh, Dw = (int(i)-1 for i in input().split())
A = [input() for i in range(H)]
V = [[-1]*W for i in range(H)] # V[h][w]を頂点iとする
d = ((1, 0), (0, 1), (-1, 0), (0, -1))
def bfs_2d(sy, sx, v):
que = deque()
V[sy][sx] = v
que.append((sy, sx))
while que:
uh, uw = que.popleft()
for dy, dx in d:
next_h = uh + dy
next_w = uw + dx
if not(0 <= next_h < H and 0 <= next_w < W):
continue
if V[next_h][next_w] != -1:
continue
if A[next_h][next_w] == '#':
continue
V[next_h][next_w] = v
que.append((next_h, next_w))
# グループ分け
vertex = 0
for h in range(H):
for w in range(W):
if A[h][w] == "#" or V[h][w] != -1:
continue
bfs_2d(h, w, vertex)
vertex += 1
# グラフを作成、全てのマスで5*5の範囲を走査
G = [[] for _ in range(vertex)]
used = [set() for _ in range(vertex)]
for h in range(H):
for w in range(W):
if A[h][w] == "#":
continue
for dh in range(-2, 3):
for dw in range(-2, 3):
if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
continue
if A[h+dh][w+dw] == "#":
continue
if V[h][w] == V[h+dh][w+dw]:
continue
if V[h+dh][w+dw] in used[V[h][w]]:
continue
G[V[h][w]].append((V[h+dh][w+dw]))
used[V[h][w]].add((V[h+dh][w+dw]))
# for h in range(H):
# print(V[h])
# for i in range(vertex):
# print(G[i])
# スタートからゴールまでbfsして最短距離を求める
s = V[Ch][Cw]
g = V[Dh][Dw]
dist = [-1 for _ in range(vertex)]
que = deque()
dist[s] = 0
que.append(s)
while que:
u = que.popleft()
for v in G[u]:
if dist[v] != -1:
continue
dist[v] = dist[u] + 1
que.append(v)
print(dist[g])
if __name__ == '__main__':
main()
グループ分け，つまり連結成分ごとに考え，縮約してグラフを作る考察がきれいにできて気持ちよかった．ただBFSをバグらせていてとても時間をかけてしまった，もったいない……．バグは，スタートマスが頂点0から始まる，としてBFSを書いてしまっていた感じ．これのせいでTLEが出ていたから，マス(h,w)がどの頂点に属するかを持つ二次元配列Vを一次元にしたり，キューに突っ込んでいたタプルを整数に直したりと†定数倍高速化†も頑張ったのだけれど，そういう工夫は今回必要なかったらしい（ABC174 Fとかは必要だった）．
ちなみにBFSは自分はこう書くのだけれど，
def bfs(s): que = deque([]) dist = [INF]*N dist[s] = 0 que.append(s) while que: pos = que.popleft() for v in G[pos]: if dist[v] != INF: continue dist[v] = dist[pos] + 1 que.append(v)
先日こんなツイートを見た．これ壊れないんだ……（びっくり）．
想定解法は01BFSらしいので，アルメリアさんの記事を読んでそれでも解くつもり．
（8/23 22:15追記） 01BFSと全マスについて，各5×5マスを走査するだけでいいダイクストラでも解いた．ダイクストラはちょっと遅くなるけど，間に合うしメモリ使用量は減った．
01BFSはdeque()の両端から追加していくBFSだった．アルメリアさんの記事にあるようにdequeを一本用意するか，もしくは競プロフレンズさんのツイートにあるように，コストの種類数だけキューを用意する（こっちのがいろいろできそう，0123BFSとか？）．
ダイクストラのコード
# ダイクストラ
INF = 10**9 + 7
def main():
from heapq import heappop, heappush
H, W = (int(i) for i in input().split())
Ch, Cw = (int(i)-1 for i in input().split())
Dh, Dw = (int(i)-1 for i in input().split())
A = [input() for i in range(H)]
dist = [[INF]*W for _ in range(H)]
dist[Ch][Cw] = 0
que = [(0, Ch*W + Cw)]
while que:
u_dist, u = heappop(que)
uh, uw = u//W, u % W
if dist[uh][uw] < u_dist:
continue
for dh in range(-2, 3):
for dw in range(-2, 3):
nh = uh + dh
nw = uw + dw
if nh < 0 or H <= nh or nw < 0 or W <= nw:
continue
if A[nh][nw] == "#":
continue
cost = 0 if abs(dh) + abs(dw) <= 1 else 1
if dist[nh][nw] > dist[uh][uw] + cost:
dist[nh][nw] = dist[uh][uw] + cost
heappush(que, (dist[nh][nw], nh*W + nw))
if dist[Dh][Dw] == INF:
print(-1)
else:
print(dist[Dh][Dw])
if __name__ == '__main__':
main()
01BFSのコード
# 01BFS
INF = 10**9 + 7
def main():
from collections import deque
H, W = (int(i) for i in input().split())
Ch, Cw = (int(i)-1 for i in input().split())
Dh, Dw = (int(i)-1 for i in input().split())
A = [input() for i in range(H)]
def bfs_2d(c, sy, sx, gh, gw, H, W):
que0 = deque()
que1 = deque()
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
que0.append((sy, sx))
while que0 or que1:
if que0:
uh, uw = que0.popleft()
else:
uh, uw = que1.popleft()
for dh in range(-2, 3):
for dw in range(-2, 3):
next_h = uh + dh
next_w = uw + dw
cost = 0 if abs(dh) + abs(dw) <= 1 else 1
if not(0 <= next_h < H and 0 <= next_w < W):
continue
if c[next_h][next_w] == "#":
continue
if dist[next_h][next_w] > dist[uh][uw] + cost:
# ここダイクストラに似てるな～と思いました
dist[next_h][next_w] = dist[uh][uw] + cost
if cost == 0:
que0.append((next_h, next_w))
else:
que1.append((next_h, next_w))
return dist[gh][gw] if dist[gh][gw] != INF else -1
ans = bfs_2d(A, Ch, Cw, Dh, Dw, H, W)
print(ans)
if __name__ == '__main__':
main()
-
一瞬「ん？」ってなりませんか？clar飛ばそうかと迷った（実際飛んでたし）．サンプルを見て考えたり質問タブに気づけるとわかる．それでもわからなかったら自分でも質問飛ばすといいんだろうな（まだコンテスト中に質問したことなし）．↩
Codeforces Round #661 (Div. 3)
バチャをした．ABCD4完（３ペナ）．AとDは正解の考察に行くまでに時間がかかった．問題を上手に整理しつつ，もっと早く正確に解法にたどり着きたい．
以下ACした問題ごとの感想とそのコード．
A問題
数列が与えられて，値の差の絶対値が1以下のペアのうち，小さい値を取り除く操作が可能．可能な限り操作して，数列の要素を1つにできるか判定する問題．
誤読していたのもあり，最初は一つでもほかの要素との差が全て2以上になる要素があったらダメでそれ以外はOKかな～みたいな全探索を書いて1WA．これは"1 1 3 3"で"YES"になってしまう（正解は"NO"）．
正しくは，ソートして隣り合う値の差の絶対値が全て1以下になっていれば"YES"で，そうでなければ"NO"．
コード
def main():
T = int(input())
for _ in range(T):
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
if N == 1 or all(A[i+1] - A[i] <= 1 for i in range(N-1)):
print("YES")
else:
print("NO")
if __name__ == '__main__':
main()
B問題
数列が2個与えられて，条件を満たすために必要な操作の最小回数を求める問題．条件は，と
．同じ
番目については，
でも
でもよい．操作は
を1つ減らすか，
を1つ減らすか，
と
を1つずつ減らすかの三つ．
も
も0より少なくはできない．
これは方針がパッと立って，減らすことしかできないのですべての値をそれぞれの数列の最小値にすればいい．と
を同時に減らす操作があるので，
番目の要素に必要な操作回数は
と
の大きい方．
最近似たような操作をしたなあ（これより難しかったし，コンテスト中に解けなかったけど）．
コード
def main():
Tquery = int(input())
for _ in range(Tquery):
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
ans = 0
minA = min(A)
minB = min(B)
for i in range(N):
need = max(A[i] - minA, B[i] - minB)
ans += need
print(ans)
if __name__ == '__main__':
main()
C問題
n個の値があって，できるだけ多くペアを作りたい．すべてのペアの値の和は，一定の値にしなければならない．このときのペア数の最大値を求める問題．
制約を見ると方針が立つ．それぞれの値は
であり，ペアの値の和
は[2,100]の範囲の値しか取らない．それぞれの値
が何個あるか数えておいて，和
を全探索．
1WAは答えの最小値を1にしていた…（のときはペアが作れないので答えが0になる）．
コード
def main():
Tquery = int(input())
for _ in range(Tquery):
_ = int(input())
W = [int(i) for i in input().split()]
cnt = [0]*(101)
for w in W:
cnt[w] += 1
ans = 0
for s in range(2, 101):
cur = 0
for i in range(1, s//2 + 1):
if i != s-i:
cur += min(cnt[i], cnt[s-i])
else:
cur += cnt[i]//2
ans = max(ans, cur)
print(ans)
if __name__ == '__main__':
main()
D問題
考察の方針があっちに行ったりこっちに行ったりと迷子になった．よくない．
nケタのbinaryの文字列が与えられる．これをいくつかの部分列に分解して，どの部分列でも0と1が交互に来るようにしたい．例えば，"0101"だったら，このまま条件を満たすし，"0100"だと条件を満たさないので"010"と"0"の2個の部分列に分解する．わかりやすさのために連続する部分列を分解したが，連続しない要素を抜き出して部分列にしてもよい．"0011"だったら，真ん中の"01"と両端の"01"の部分列に分解する．つまり"0"や"1"が連続して現れないように部分列を作ることが条件．そしてすべての部分列が条件を満たすような最小の分解の個数を求めるのが問題．
初めは個数だけで決まる？と考えたけど，"0101"は部分列が1，"0011"は部分列が2で違うなと気づき，すぐに方針を切り替える．ここから部分列の個数が何個になるだろう？を考えていたが，最終的に要素ごとにどの部分列に割り当てるか構築しなければいけないことは考えていなかった．反省．
サンプルだけは合うコードが書けるも，"10001011110"で5個必要と出力されるようなコードを書いて1WA（正しくは4個で十分）．
最終的な解法は，キューを二つ用意しておき，文字列を前から見ていった．"0"が来たら"1"が末尾の列に追加したいので，そのような列がキューに入っていれば追加，入っていなければ"0"を先頭にするような新しい部分列を増やすことにした．実際にキューに部分列を入れる必要はなく，何個目の部分列であるか，だけ入れて管理すればいい．
コード
def main():
from collections import deque
Tquery = int(input())
for _ in range(Tquery):
N = int(input())
S = input()
ans = [-1]*N
idx = [deque(), deque()]
teamnum = 0
for i, s in enumerate(S):
if idx[int(s) ^ 1]:
team = idx[int(s) ^ 1].popleft()
ans[i] = team
idx[int(s)].append(team)
else:
newteam = teamnum + 1
ans[i] = newteam
teamnum += 1
idx[int(s)].append(newteam)
print(teamnum)
print(*ans)
if __name__ == '__main__':
main()
なんかググってたらすごいたくさん解説が書いてありそうなサイト見つけた．なんだこれすごい．
Code Formula 2014 予選A C - 決勝進出者
何人かのコードを見た感じ，これ人によって解法違いそう．
解法
(順位，予選時期，ID)をタプルとし，heapqに入れていく． 予選ごとにheapqを見て，（取り出した値から将来負けうる人数）+ （既に通過した人数）がK未満だったらその予選時にメールを送る． 取り出した値から将来負けうる人数は，(順位 - 1)*(N - i - 1)となる．
提出コード
コード
def main():
N, K = (int(i) for i in input().split())
A = [[int(i) for i in input().split()] for j in range(N)]
from heapq import heappop, heappush
hque = []
passed = set()
for i in range(N):
ans = []
for j, a in enumerate(A[i], start=1):
# (順位，予選時期，ID)
heappush(hque, (j, i, a))
for _ in range(len(hque)):
(jj, ii, aa) = heappop(hque)
v = (jj - 1)*(N - i - 1)
if aa not in passed and len(passed) + v < K:
ans.append(aa)
passed.add(aa)
elif aa not in passed:
heappush(hque, (jj, ii, aa))
ans.sort()
print(*ans)
if __name__ == '__main__':
main()
あさかつのEで出たんだけど，通せなかったのでLorentさんのツイートを見て通した． 上のコードはPyPyだとMLEする．なんか無駄なことをしてそうな？感じもするので，他の人のコードも参考にするのがよさそう． 記事投稿時にはPyPy(7.3.0)のACがなかった．judge-update-202004以前の提出も見たい場合，この拡張を入れるのがおすすめ．
TopCoder SRM 788 Div.2 感想
初めてのTopCoder．運がよかったのか青になった．やったね．
TopCoderのSRMは，AtCoderやCodeForcesよりもコンテストサイトがわかりにくかったり，入出力の形式が違ったりで少し参加しにくかったです．事前に過去問を解いたり，最初の一回目は慣れのために手探りでやったり，みたいなことが必要かもしれません．
かっつさんの記事を参考に環境構築．昔から使われている方がいいかもしれない，と思ってjavaappletを入れて参戦しました（ただコンテスト終了後のTLを見た感じweb arenaで参加していた人も多かったみたい？web arena参加した人でコンテスト中に困ったことがあった人もいなさそうだった）．
コンテストの説明とかも書こうと思ったけれど，かっつさんの記事に書いてあるからそっちを読めばいいですね…（？）． あとはコンテスト前に参考になった診断人さんのリツイートやtatyamさんのツイートを置いておきます．
Python2系について詳しくないんですが，なんか普段通りPython 3の気持ちで書いても動きました（？）．かっつさんの記事の紹介にあるGreedというプラグインのおかげで，勝手にクラスやテストコードが生成されたのがありがたかったです（最初デバッグ方法がわかりませんでしたが）．ただし，提出前にテストコードを消すのを忘れないようにしましょう．Challenge phaseやSystem Testがあるので，いつも以上に与えられる入力でバグらないかをチェックしてから出すといい気がします．Python使いの人で，普段クラスを書かない人（僕など）はクラスの書き方も確認しておきましょう（selfつけるの忘れないとか）．
以下問題ごとの感想とコードです．
NextOlympics（easy）
テストコード貼り付けたまま一回提出してもったいなかったです． Pythonにはdatetimeモジュールがあるので，これを使いました． whileを回しましたが，2021.07.23と差分を取るだけでよかったですね．
ACコード
# -*- coding: utf-8 -*-
import datetime
class NextOlympics:
def countDays(self, today):
A = today
T = datetime.date(int(A[0:4]), int(A[5:7]), int(A[8:]))
y, m, d = T.year, T.month, T.day
ans = 0
while not (y == 2021 and m == 7 and d == 23):
T += datetime.timedelta(days=1)
ans += 1
y, m, d = T.year, T.month, T.day
return ans
StarsInTheSky（medium）
いくつか座標が与えられて，条件を満たす部分集合を数え上げる問題です．サンプル1を見て問題を理解しました． bit全探索をすぐにやればよかったんですけど，ちょっともたもたしてしまい…うー，もったいない． ある星の組合せに対して，それ以外の星を含まないような長方形にできているかを毎回チェックして数えました．
ACコード
# -*- coding: utf-8 -*-
class StarsInTheSky:
def countPictures(self, N, X, Y):
ans = 0
for bit in range(1, 1 << N):
cur_not = []
XL = 1000000005
XR = -1
YL = 1000000005
YR = -1
for i in range(N):
if bit & (1 << i):
if XL > X[i]:
XL = X[i]
if XR < X[i]:
XR = X[i]
if YL > Y[i]:
YL = Y[i]
if YR < Y[i]:
YR = Y[i]
else:
cur_not.append(i)
flag = True
for i in cur_not:
if XL <= X[i] <= XR and YL <= Y[i] <= YR:
flag = False
break
if flag:
ans += 1
return ans
SquareCityWalking（hard）
サンプルは通ったんですけど，システスで落ちました（えーん）． 適当にダイクストラしたんですけど，うーん．なんか間違えたらしい．明日復習します．
WAコード
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
class SquareCityWalking:
def gcd(self, x, y):
if y == 0:
return x
while y != 0:
x, y = y, x % y
return x
def largestGCD(self, N, A):
A = list(A)
g = self.gcd(A[0], A[(N-1)*N+(N-1)])
for i in range(N):
for j in range(N):
v = self.gcd(g, A[i*N+j])
A[i*N+j] = v
d = [[0 for j in range(N)] for i in range(N)]
d[0][0] = g
que = [(-d[0][0], (0, 0))]
heapify(que)
finished = set()
dyx = ((0, 1), (1, 0))
while que:
u = heappop(que)
u = (-u[0], u[1])
while que and u[1] in finished:
u = heappop(que)
for dy, dx in dyx:
next_y = u[1][0] + dy
next_x = u[1][1] + dx
v = (next_y, next_x)
if not(0 <= next_y < N and 0 <= next_x < N):
continue
if v in finished:
continue
if d[v[0]][v[1]] < self.gcd(u[0], A[v[0]*N+v[1]]):
d[v[0]][v[1]] = self.gcd(u[0], A[v[0]*N+v[1]])
heappush(que, (-d[v[0]][v[1]], v))
finished.add(u[1])
return d[N-1][N-1]
公式解説はココ．
Codeforces Round #636 (Div. 3)
バチャをした！べるさんとしふとさんとはてぃーぽったーさんとnok0さんとmedoさんとkumakumaaaaaさんとサマリ6さんと並走！
ABC3完．Aでめちゃくちゃ苦戦した．悔しい！！！！！！！！
以下問題ごとの感想とACコード．
A問題
解説見たらなんで解けなかったんだろう…という気持ちになった．
全然左辺をくくろうという気持ちにならなかったんだよな…nの約数を求めるなどしていた．本当に悔しいな． たぶんコンテストでは，20分くらいかけて2WA出してて方針に自信がないときは一回飛ばした方がよさそう．いや，飛ばすべき（ABCのBとかでこういうの来たら怖いな）．
コード
def main():
T = int(input())
A = [2**i-1 for i in range(2, 32)]
for _ in range(T):
N = int(input())
for a in A:
if N % a == 0:
print(N//a)
break
if __name__ == '__main__':
main()
B問題
Aを飛ばして，比較的サクッと解法が浮かんだ（しかし2WA）．うーん，一つ前が解けてなくても平常心を保ちたい．
Nを2で割ったものを，さらに2で割った余りが1ならば"NO"．つまり4の倍数でないときは"NO"．これは後半の奇数のみの和を前半の和と等しくするために，後半の要素が偶数個でなければならないから． 2の倍数でn//2個適当に前半を構築し，aの要素から1引いたものでn//2-1個とaの和とbの和の差で1個の合計n//2個で後半を構築する．
コード
def main():
T = int(input())
for _ in range(T):
N = int(input())
if (N//2) % 2 == 1:
print("NO")
else:
print("YES")
A = [2*i for i in range(1, N//2+1)]
B = [a-1 for a in A[:-1]]
B.append(sum(A) - sum(B))
print(*A, *B)
if __name__ == '__main__':
main()
C問題
一番わかりやすい． 正が連続するところと負が連続するところでそれぞれ数列を見て，それぞれのmaxを取ってきて和を求めればよい． alternating subsequence ってなんだ…？って読んでるとき一瞬思ったけど，交代行列とか交代級数のalternatingか～って途中で気づいた．
コード
def main():
T = int(input())
for _ in range(T):
_ = int(input())
A = [int(i) for i in input().split()]
ans = 0
cur_max = A[0]
posi = True if A[0] > 0 else False
for a in A[1:]:
if posi:
if a > 0:
cur_max = max(cur_max, a)
else:
ans += cur_max
posi = False
cur_max = a
else:
if a < 0:
cur_max = max(cur_max, a)
else:
ans += cur_max
posi = True
cur_max = a
print(ans + cur_max)
if __name__ == '__main__':
main()
D問題
バチャ後に解説AC．これ難しくないか？？？？？
問題概要
長さnの数列aと整数kが与えられる．前からi番目と後ろからi番目をペアにして，それぞれ和を計算する（）．ただし，和はある値xにしたい．xはすべてのペアで共通の値である．数列aの各要素を変更してよいとき，変更しなければいけない要素の個数は最小で何個か求めよ．ただし，数列aの要素
は
の範囲の整数値を取るとする（変更後も！）．
思考過程
とりあえず各ペアの和は取りたくなるので，Counter()でペアの和それぞれが何個あるか数える．どれかにできるのかな～って思ったけど，上手く計算できそうにない．困ったので解説を見た．
解法
各ペアの和xは，区間]のいずれかの値を取る．xの値を決め打ったとき，変更しなければいけない要素の個数が高速にわかると問題が解ける．
xの値を固定したときに，各ペアについて考える操作は3パターンある． 1. 変更する要素はない．すでにペアの和がxになっている． 2. 1つ要素を変更する． 3. 2つ要素を変更する．
1.は思考過程に書いたように，実際のペアの和を計算し，それぞれの和が何個あるか数えるとわかる（和xになるペアを数える）．
2.は，各ペアが取りうる和の範囲を考える．ペアの和が一番小さくなるのは
のとき（値の大きい方を1に置き換えた）．一番大きくなるのは，
のとき（値の大きい方をkに置き換えた）．この2つの間の和は全部作れて，あるペア
が1つ要素を変更したときの取りうる和の範囲がわかった．ただしこれは要素を変更しなかったとき（0個要素を変更したとき）の和も含んでいることに注意する．そして，これを各ペアについて和を足し合わせると，和をxにしたときの要素を1個以下変更するペアの数がわかる．
1.を保存しているリストをcnt，2.を保存しているリストをSとする．それぞれについて，和をxにしたときに要素を前者なら0個，後者なら1個以下変更するペアの個数を，
と書く．
すると，3.は和をxにしたときに(N//2 -)個が変更しなければいけないペアの数とわかる．
ここまで頑張ると，各xについて変更しなければいけない要素の個数はであるから，各xについてこれを計算して最小値が答え．
反省
各ペアの和の範囲は考えるべきだった．その和にできるか？みたいなのをO(1)で判定できたら和の範囲でループを回せばよい…までは思考できるようにしたかった．ここまで考察が進んだら，和xを固定したときに取りうる状態を考えたり，範囲を考えたくなる気持ちはあったので，うまくまとめあげて解法のように考えを進めていきたい．次は解きたいなあ．
コード
def main():
from collections import Counter
from itertools import accumulate
T = int(input())
for _ in range(T):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
# ペアの和について，その和になるペアがいくつあるか数える
c = Counter()
for i in range(N//2):
c[A[i] + A[-(i+1)]] += 1
# ペアの要素を1つ以下変えたときに，各ペアが取りうる区間を計算
# いもす法を使って，ペアの要素を1つ以下変更するだけで各和xにできるペアの数を計算
S = [0]*(2*K+5)
for i in range(N//2):
mi = min(A[i], A[-(i+1)]) + 1
ma = max(A[i], A[-(i+1)]) + K
S[mi] += 1
S[ma + 1] -= 1
S = list(accumulate(S))
# 各xについて変更しなければいけない数を計算．最小が答え
ans = 3*10**5
for x in range(2, 2*K+1):
cur = (S[x] - c[x]) + (N//2 - S[x])*2
ans = min(ans, cur)
print(ans)
if __name__ == '__main__':
main()
Codeforces Round #656 (Div. 3)
ABCD4完．Eはコンテスト後にnok0さんに教えてもらって通した！
以下問題ごとの感想とACコード．
A問題
サンプルが親切なので，じっと見ると大きい方から2個が一致していればよさそうなことに気づく． 解は，小さい数を2個と大きい数が1個の組である．小さい数が2個ないと，その小さい数が作れないので． コンテスト中は"any order"に気づかなくて，順番考えて解を出力してた．Bより難しい…．1
コード
def main():
T = int(input())
for _ in range(T):
A = [int(i) for i in input().split()]
B = sorted(A)
if B[1] == B[2]:
print("YES")
print(B[0], B[0], B[2])
else:
print("NO")
if __name__ == '__main__':
main()
B問題
こどふぉあるある，inputとoutputとサンプルだけ見て問題を読んでいない．
でも"It is guaranteed that the answer exists and is unique."に安心してコーナーとかなさそう！wと思って提出した．
set()を用意して，初めに現れたときだけリストに追加．for文回し終わったらリストを出力．
コード
def main():
T = int(input())
for _ in range(T):
_ = int(input())
A = [int(i) for i in input().split()]
B = set()
ans = []
for a in A:
if a in B:
continue
ans.append(a)
B.add(a)
print(*ans)
if __name__ == '__main__':
main()
C問題
こどふぉあるある，問題文を4，5回読んだ（他の人にとってはあるあるではないですか？僕に限られるかもしれません）． 与えられた数列の先頭から，要素をいくつか取り除いて，残った数列から単調増加数列を作れるようにしたい． 最小で取り除かなければいけない要素はいくつか？という問題．
後ろから，単調減少している長さか，単調増加してから単調減少している数列の大きさを求める． その数列が，"残った数列"であり，これなら単調増加数列を作れる． (与えられた数列の大きさN) - ("残った数列"の大きさ)が，求める取り除く要素数になるのでクエリごとにこれを出力． なんかAtCoderのある問題をコンテスト中に思い出した．
コード
def main():
T = int(input())
for _ in range(T):
N = int(input())
A = [int(i) for i in input().split()][::-1]
flag = False
pre = A[0]
cnt = 1
for a in A[1:]:
if not flag:
if a >= pre:
pass
else:
flag = True
else:
if a <= pre:
pass
else:
break
pre = a
cnt += 1
print(N - cnt)
if __name__ == '__main__':
main()
D問題
これ解けたの嬉しい． 再帰で一番少ない数を計算する．
思考過程としては，問題文を読んでいて，*-good（*は任意の英小文字）の定義がまず再帰っぽいなと思った．操作はを好きな文字に変えること，答えは必ず存在することを確認し，方針を考え始めた．
であり，'a'から(k+1)種類文字を使うんだな～と気づき（k = 3ならa, b, c, dまで使う），とりあえずascii_lowercaseをimportしながら続きを考える．k = 3のときのサンプルを書きだして，どこが'a'になるかから決めるのか，どこが'd'になるかから決めるのかをちょっと悩む．もし'aaaa'を前半にするなら，後半で'dcbb'みたいなのを作らなきゃいけなくて～，辺りまで考えて，「これ再帰でやればいいんじゃない？」と気づく．前半を'a'で埋める場合に変更する要素数を数えて，後半については再帰の次の処理で考える．同じように，後半を'a'で埋める場合に変更する要素数を数えて，前半については再帰の次の処理で考える．深さを持っておけば，その時点で何の文字にしたいか，も割と簡単に持てるし，これだ！！と実装する．終了条件を最初N == 0にしてサンプルが合わなくて，N == 1のときに分岐して返すようにしたら上手くいった．
コード
def main():
from string import ascii_lowercase
dic = {i: a for i, a in enumerate(ascii_lowercase)}
T = int(input())
def dfs(N, S, i=0):
if N == 1:
return 1 if dic[i] != S[0] else 0
ret1, ret2 = 0, 0
ret1 = sum(dic[i] != s for s in S[N//2:])
ret2 = sum(dic[i] != s for s in S[:N//2])
ret = min(dfs(N//2, S[:N//2], i+1)+ret1,
dfs(N//2, S[N//2:], i+1)+ret2)
return ret
for _ in range(T):
N = int(input())
S = [s for s in input()]
print(dfs(N, S))
if __name__ == '__main__':
main()
E問題
トポソは思いつけたのに～～～！解けなかった悔しい！
無向辺は大胆に消してしまおう！
コード
def main():
from collections import deque
T = int(input())
for _ in range(T):
N, M = (int(i) for i in input().split())
edge = [[] for _ in range(N)]
edges = []
direct = [0]*M
deg = [0]*N
for m in range(M):
t, a, b = (int(i) for i in input().split())
a -= 1
b -= 1
if t == 1:
edge[a].append(b)
deg[b] += 1 # in-degree
direct[m] = t
edges.append((a, b))
que = deque()
order = 0
ans = []
for i in range(N):
if deg[i] == 0:
que.append(i) # root
ans.append((i, order))
order += 1
while que:
u = que.popleft()
for v in edge[u]:
deg[v] -= 1
if deg[v] == 0:
que.append(v)
ans.append((v, order))
order += 1
ans.sort(key=lambda p: p[1])
# トポソできなければ閉路がある
# トポソできれば，トポソでつけた頂点の順番にそって無向辺に向き付けすればOK
if len(ans) == N:
print("YES")
dic = {a: s for a, s in ans}
for m, (x, y) in enumerate(edges):
if direct[m] == 1:
print(x+1, y+1)
else:
if dic[x] < dic[y]:
print(x+1, y+1)
else:
print(y+1, x+1)
else:
print("NO")
if __name__ == '__main__':
main()
-
なんかpiddyさんがもっと簡単そうにやってた．https://twitter.com/87___ka/status/1284191965412646912?s=20↩
DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2
思考過程
与えられた整数のそれぞれについて，他の整数
のそれぞれと積を取り，
の倍数であるか確認する解法がまず思いつきます．
が，計算量がO(
)になり，今回の入力サイズは
となるのでTLEしてしまいます．
ここでサンプル1を見てみましょう．
4 6 1 3 2 6
積を考えたいので，それぞれの要素に何をかければの倍数になるか考えます．
すると，
には
をかければいいことに気づきます．
は，
の約数です．必要そうなので，ここら辺で
の約数をとりあえず列挙しておきます．
では前処理として，約数ごとに
番目以降のその約数の個数を計算して，配列に保存しておけばいいのではないでしょうか．
これができたら，
を順にみていって，かけたらいい
の個数が
で求まり，答えがわかります．
前処理をした配列を値とし，対応する約数をキーとした辞書を持っておけば実装できそうです！
しかし残念ながらこれも前処理に
かかり，今回の入力だとTLEしてしまいます…．
解法
の約数について考えるのはいいことでした．さらに
の約数なら高々1500個くらいで抑えられるので1，
ならしていいです．ここで，
はi番目の
の約数とします．そして，
を
との最大公約数として持つAの要素の個数を，
ごとに数えておきます2．
以降，を
との最大公約数として持つAの要素の個数の
の個数と単に言います．
と
の個数の積を取ると，
と
の積を因数に持つペアの個数だということを発想します．ここは例を考えるとわかりやすくて，サンプルを考えましょう．サンプル1から要素を1つ増やしたものです．
5 6 1 3 2 6 4
このとき，6の約数は1, 2, 3, 6であり，1の個数は1個，2の個数は2個，3の個数は1個，6の個数は1個です．1の個数と6の個数をかけるとを含むペアは1通りです（1と6）．2の個数と3の個数をかけると，
を含むペアは2通りです（3と2，3と4）．1の個数と4の個数をかけると
を含むペアは1通りです（1と4）．
を含むペアは1通りです（2と6）．
を含むペアと，
を含むペアというのは区別します3．
これに対し，と
をかけて
の約数になるようなペアだけ数え上げればいいです．具体的には，約数を二重ループで回して，順番を気にせずにかけて
の約数になるなら和を取ってしまいます．そうすると
を含むペアと
を含むペアが同じなので，最終的な和は答えより2倍大きい値になります．ちょうど2倍になっているので2で割ってあげると求めたい答えが得られます．
ただし，一つ注意する点があります．6の個数と6の個数をかけるとを含むペアの総数が得られるとしたいですが，同じものを2つ選んだペアも数え上げてしまっているので，答えが正しいものより大きくなってしまします（実際，上のサンプルでは6の個数は1個でペアはできないのに，
を含むペアを一つ数えてあげてしまうことになります）．これを避けるために，
と
が同じものだったときは，
を足してあげればいいです．これは
という集合から2つ選ぶという組合せの総数と考えることができます4．
提出コード
提出コード
from math import gcd
import sys
input = sys.stdin.buffer.readline
def main():
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
def enum_divisors(n):
# 約数列挙
divs = []
for i in range(1, n+1):
if i*i > n:
break
if n % i == 0:
divs.append(i)
if n//i != i:
# i が平方数でない
divs.append(n//i)
return divs
divs = enum_divisors(K)
G = [gcd(a, K) for a in A]
B = {d: 0 for d in divs}
for g in G:
B[g] += 1
ans = 0
for g in divs:
for rg in divs:
if (g*rg) % K == 0:
ans += B[g] * (B[rg] - (g == rg))
print(ans//2)
if __name__ == '__main__':
main()
僕はこの問題を解説ACしたのですが，解説pdfを読んでも全然わからなかったのでTwitterで質問しまくりました．はてぃーぽったーさん，茶碗蒸しさんありがとうございます．
