Skip to content

Instantly share code, notes, and snippets.

View maehrm's full-sized avatar

Masahide Maehara maehrm

8 followers · 0 following
View GitHub Profile
@maehrm
maehrm / abc287_e.py
Created March 15, 2026 01:44
E - Karuta https://atcoder.jp/contests/abc287/tasks/abc287_e
def get_lcp(str1, str2):
ret = 0
for s1, s2 in zip(str1, str2):
if s1 != s2:
break
ret += 1
return ret
N = int(input())
@maehrm
maehrm / abc024_c.py
Created March 15, 2026 00:32
C - 民族大移動 https://atcoder.jp/contests/abc024/tasks/abc024_c
N, D, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(D)]
ST = [list(map(int, input().split())) for _ in range(K)]
ans = [-1] * K
for i in range(D): # i日目
l, r = LR[i]
for j in range(K): # j番目の民族の移動
if ans[j] != -1:
continue
@maehrm
maehrm / abc217_e.py
Last active March 14, 2026 09:41
E - Sorting Queries https://atcoder.jp/contests/abc217/tasks/abc217_e
import heapq
from collections import deque
queA = deque() # まだソートされてない配列Aを表現
heapA = [] # ソート済みの配列Aを表現
Q = int(input())
for _ in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
x = query[1]
@maehrm
maehrm / abc325_e.py
Created March 14, 2026 01:50
E - Our clients, please wait a moment https://atcoder.jp/contests/abc325/tasks/abc325_e
import heapq
def dijkstra(start_node, G): # ダイクストラ法
dist = [float("inf")] * N
dist[start_node] = 0
que = [(0, start_node)]
while que:
d, pos = heapq.heappop(que)
if d > dist[pos]: # ここで速度改善!
@maehrm
maehrm / abc191_c.py
Created March 14, 2026 01:11
C - Digital Graffiti https://atcoder.jp/contests/abc191/tasks/abc191_c
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = 0
for i in range(H - 1):
for j in range(W - 1):
cnt = 0
for di, dj in ((0, 0), (0, 1), (1, 0), (1, 1)):
if S[i + di][j + dj] == "#":
cnt += 1
if cnt == 1 or cnt == 3:
@maehrm
maehrm / abc308_e.py
Created March 13, 2026 20:08
E - MEX https://atcoder.jp/contests/abc308/tasks/abc308_e
def get_mex(a, b, c):
mex = [False] * 4
mex[a] = mex[b] = mex[c] = True
for i in range(4):
if mex[i]:
continue
return i
N = int(input())
@maehrm
maehrm / abc263_d.py
Created March 13, 2026 20:07
D - Left Right Operation https://atcoder.jp/contests/abc263/tasks/abc263_d
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
revA = A[::-1] # 逆順にしておく
# dpl[i]: 左からi番目まで見たときの最小値
# dpr[i]: 右からi番目まで見たときの最小値
dpl = [0] * (N + 1)
dpr = [0] * (N + 1)
for i in range(N):
@maehrm
maehrm / abc229_e.py
Created March 12, 2026 11:03
E - Graph Destruction https://atcoder.jp/contests/abc229/tasks/abc229_e
from atcoder.dsu import DSU
N, M = map(int, input().split())
G = [[] * N for _ in range(N)]
for _ in range(M):
a, b = map(lambda x: int(x) - 1, input().split())
G[a].append(b)
dsu = DSU(N)
curr = 0
@maehrm
maehrm / abc418_d.py
Created March 12, 2026 11:02
D - XNOR Operation https://atcoder.jp/contests/abc418/tasks/abc418_d
N = int(input())
T = input()
# dp[r][0] : 0が偶数個(結果が1になる)
# dp[r][1] : 0が奇数個(結果が0になる)
dp = [[0] * 2 for _ in range(N + 1)]
for r in range(1, N + 1):
if T[r - 1] == "0":
dp[r][0] = dp[r - 1][1]
@maehrm
maehrm / abc318_d.py
Created March 11, 2026 10:54
D - General Weighted Max Matching https://atcoder.jp/contests/abc318/tasks/abc318_d
N = int(input())
D = [[0] * N for _ in range(N)]
for i in range(N - 1):
d = list(map(int, input().split()))
for j in range(len(d)):
D[i][i + j + 1] = d[j]
D[i + j + 1][i] = d[j]
dp = [0] * (1 << N)
for bit in range(1 << N):