CODE FESTIVAL 2014 Easy D - 枕決め
知らないと解けないなと思ったのでメモ。参考
CODE FESTIVAL 2014 あさプロMiddle : B - 枕決め - kmjp's blog
N人の人とM個の枕がある。
N人はそれぞれ高さがX[i]以上Y[i]以下の枕が好みであり、そのような枕を１個使いたい。
M個の枕の高さA[0] ~ A[m]が与えられるとき、最大何人が好みの枕を使えるか。
解き方
まず (X[i], Y[i]) を List[x[i]].append(Y[i]) として前処理する。
次に高さの下限1から上限100000まで以下の処理を行う。今見ている高さをhとすると：
最初に作った配列を参照し、X[i]==hであるような人がいたら、(List[h] != [ ] であるなら）
List[h] の要素を heap に入れる。
heap から A[i]==h な枕の数だけ、heap からY[i]の低い順に枕を割り当てる。
heap には「h以上の枕が好みの人が、Y[i]の低い順に入っている」という状態にしておくことで、以後登場する枕をY[i]の低い順に割り当てることができる。
X ≦ Y であり、h(X) の小さい順に調べているので、heappop したときに、Y[i] ≧ h ならば
その i さんは X[i] ≦ h ≦ Y[i] を満たす枕が存在し、割り当てることが最適といえる。
逆に、Y[i] ＜ h ならば好みの枕は割り当てないことが最適といえる。
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from heapq import heapify,heappop,heappush n,m = map(int,readline().split()) xy = [list(map(int,readline().split())) for i in range(n)] a = [int(readline()) for i in range(m)] A = [0]*100001; Y = [[] for i in range(100001)] for i in a: A[i] += 1 for x,y in xy: Y[x].append(y) que = []; heapify(que) ans = 0 for h in range(1,100001): for y in Y[h]: heappush(que,y) while A[h]: if que == []: break yy = heappop(que) if yy >= h: ans += 1 A[h] -= 1 print(ans)
abc 187 E - Through Path
"「ある頂点の子孫でない頂点に xを足す」は、
「根の子孫に xを足す」と「ある頂点の子孫に -xを足す」に分けることができるので、
全てのクエリを「ある頂点の子孫に x を足す」の形に帰着することができます。"
かしこい。は？となりながら解説の言うとおりにやってみたら確かにできた。
２つ条件があって、一つが簡単に書けるときは、もう一方をその条件に帰着できないか考えるのが大事なのかなと思った。あと木の上で総和を求めていくのも初だった。
import sys input = sys.stdin.readline from collections import deque n = int(input()) h = [0]*n g = [[] * n for i in range(n)] for i in range(n-1): u, v = map(int, input().split()) u -= 1 v -= 1 g[u].append(v) g[v].append(u) h[i] = (u,v) que = deque() que.append((0,1)) dep = [0]*n chk = [False]*n chk[0] = True cnt = 1 while que: now,p = que.popleft() if cnt == n: break for i in g[now]: if not chk[i]: dep[i] = p chk[i] = True cnt += 1 que.append((i,p+1)) ans = [0]*n q = int(input()) for i in range(q): t,e,x = map(int, input().split()) e -= 1 a,b = h[e] if t == 2: a,b = b,a if dep[a] < dep[b]: ans[b] -= x ans[0] += x else: ans[a] += x que = deque() que.append(0) chk = [False]*n chk[0] = True cnt = 1 while que: now = que.popleft() if cnt == n: break for i in g[now]: if not chk[i]: ans[i] += ans[now] chk[i] = True cnt += 1 que.append(i) print(*ans,sep='\n')
abc 100 D - Patisserie ABC (python)
解けなかった。
発想１．(Xi + Xj + Xk) + (Yi + Yj + Yk) + (Zi + Zj + Zk) を
(Xi + Yi + Zi) + (Xj + Yj + Zj) + (Xk + Yk + Zk) とみて考える。
これは添え字が同じになるように移項するのと同じ発想なので思いつくべきだった。
発想２．- (Xi + Xj + Xk) + (Yi + Yj + Yk) - (Zi + Zj + Zk)
= (- Xi + Yi - Zi) + (- Xj + Yj - Zj) + (- Xk + Yk - Zk)
確かにとはなったけど、自力では厳しい考えだった。
なので、X, Y, Z それぞれが + か - かの８通りで ± X ± Y ± Z を求めておいて、降順ソートして m 個の和を求めたうちの最大値を出せば終わり。
numpy 使うと楽に書ける。
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np n,m = map(int,readline().split()) chk = np.empty((n,8),dtype=np.int64) # n行8列の初期リスト for i in range(n): a,b,c = map(int,readline().split()) chk[i][0] = a+b+c chk[i][1] = a+b-c chk[i][2] = a-b+c chk[i][3] = a-b-c chk[i][4] = -a+b+c chk[i][5] = -a-b+c chk[i][6] = -a+b-c chk[i][7] = -a-b-c chk = np.sort(chk,axis=0)[::-1] # 8列分一括で列ごとに降順ソート chk = np.resize(chk,(m,8)) # 上からm個まであればいい print(max(np.sum(chk,axis=0))) # 列ごとに合計値求めた中の最大値が答え
abc 104 c All Green (python)
ずっとほったらかしていた問題。
dfs で全探索するのだけど、愚直に計算すると間に合わない。
• 中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。
• 中途半端に解く配点があるなら、それは完全に解く配点以外の配点の中で最も高い配点である。
の２点に気づいて探索する候補を絞る必要がある。
実装は dfs(a,b,c,d) として、
a = 今解こうとしている配点
b = 今まで解いた問題の配点の総和
c = 今まで解いた問題数
d = 中途半端に解いたことがあるか
で全探索した。２つ目の条件を上手く満たすように配点を高い順に a を調べた。
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines sys.setrecursionlimit(10**7) n,k = list(map(int,readline().split())) k //= 100 l = [] for i in range(n): array = list(map(int,readline().split())) l.append(array) ans = float('inf') def f(a,b,c,d): global ans if a == 0: if b >= k: ans = min(ans,c) return if c >= ans: return if b >= k: ans = min(ans,c) return else: if d == 0: g = min(l[a-1][0],(k-b)//a+2) return [f(a-1,b+a*i,c+i,1) for i in range(1,g)],f(a-1,b,c,d),f(a-1,b+a*(l[a-1][0])+(l[a-1][1])//100,c+l[a-1][0],d) else: return f(a-1,b,c,d),f(a-1,b+a*(l[a-1][0])+(l[a-1][1])//100,c+l[a-1][0],d) f(n,0,0,0) print(ans)
abc 175 E - Picking Goods (python)
３次元 dp するときに、r,c,k のうち k だけ、計算量が小さいときは、
dp = [[[0]*c for _ in range(r)] for _ in range(k)]
と書いた方が実行時間が短くなるという知見を得た。というかこう書かないと TLE するのだがなぜ？
def main(): import sys r,c,k = map(int, input().split()) p= [[0]*c for _ in range(r)] for s in sys.stdin.readlines(): x,y,z = map(int,s.split()) p[x-1][y-1] = z ans = [[[0]*c for _ in range(r)] for _ in range(4)] if p[0][0] > 0: ans[1][0][0] = p[0][0] for R in range(r): for C in range(c): for d in range(4): a = ans[d][R][C] if R < r-1: ans[0][R+1][C] = max(a,ans[0][R+1][C]) ans[1][R+1][C] = max(a+p[R+1][C],ans[1][R+1][C]) if C < c-1: ans[d][R][C+1] = max(a,ans[d][R][C+1]) if d < 3: ans[d+1][R][C+1] = max(a+p[R][C+1],ans[d+1][R][C+1]) dp = 0 for i in range(4): dp = max(ans[i][-1][-1],dp) print(dp) if __name__ == '__main__': main()
※TLEするやつ↓。p の順番を変えただけ。
Submission #18495208 - AtCoder Beginner Contest 175
abc 176 D - Wizard in Maze (python)
atcoder 再開。水色になった。
01-bfs というやつらしい。+0 を append で、+1 に遷移するものを appendleft でdeque に入れてあげると、O(1) で heap みたいなことができる。heap で回したら TLE した。
よくある bfs や今回初めて書いた 5*5 の移動をメモしたかったのでまとめた。
import sys input = sys.stdin.readline h,w = map(int,input().split()) sh,sw = map(int,input().split()) gh,gw = map(int,input().split()) a = [list(input()) for i in range(h)] d = [[10**6]*w for i in range(h)] dh = [1, 0, -1, 0] dw = [0, 1, 0, -1] dx = [0,0,1,1,1,1,2,2,2,2,2,-1,-1,-1,-1,-2,-2,-2,-2,-2] dy = [2,-2,2,1,-1,-2,-2,-1,0,1,2,2,1,-1,-2,2,1,0,-1,-2] from collections import deque que = deque() que.append((sh-1,sw-1,0)) d[sh-1][sw-1] = 0 while que: y,x,p = que.pop() if y == gh and x == gw: break for i in range(4): nw = x + dw[i] nh = y + dh[i] if 0 <= nw < w and 0 <= nh < h and a[nh][nw] != "#" and d[nh][nw] > p: que.append((nh,nw,p)) d[nh][nw] = p for j in range(20): nx = x + dx[j] ny = y + dy[j] if 0 <= nx < w and 0 <= ny < h and a[ny][nx] != "#" and d[ny][nx] > p+1: que.appendleft((ny,nx,p+1)) d[ny][nx] = p+1 if d[gh-1][gw-1] == 10**6: print(-1) else: print(d[gh-1][gw-1])
abc 061 D - Score Attack (python)
ほぼこれ。abc 137 E - Coins Respawn (python) - aacord’s memo
頂点１からNまでに通りうる経路だけ抜き出して、その中で bellman-ford を使う。更新回数が m 回をこえたら inf を出力する。
from collections import deque def belman(s,n,w,es): d = [-float("inf")] * n #d[i] : s→iの最短距離 d[s] = 0 c = 0 while True: update = False for p,q,r in es: if d[p] != -float("inf") and d[q] < d[p] + r: d[q] = d[p] + r update = True c += 1 if c > w: return 'inf' if not update: break return d[n-1] def use_path(n,start,es): q = deque() chk = [False] * n q.append(start) chk[start] = True used = {start} while len(q) > 0: node = q.popleft() for nex in es[node]: if not chk[nex]: chk[nex] = True q.append(nex) used.add(nex) return used n,w = map(int,input().split()) es = [] l = [[] for i in range(n)] r = [[] for i in range(n)] for i in range(w): a,b,c = map(int, input().split()) a -= 1 b -= 1 l[a].append(b) r[b].append(a) es.append((a,b,c)) use = use_path(n,0,l) & use_path(n,n-1,r) ess = [(a,b,c) for a,b,c in es if a in use and b in use] print(belman(0,n,w*2,ess))
