競プロ典型90問:028 - Cluttered Paper(★4)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_ab
挑戦結果
- 挑戦日:2021/10/07
- 結果:解けた
- 時間:30分ぐらい
考えたこと
- いもす法というやつで解けるのでは?
- はっきりとおぼえていなかったけど、縦と横で累積和を取るはず
公式解説
解説を読んだふりかえり
- やっぱりいもす法で良かった
- 実装で添字をミスっていて苦しんだけど、次回はスムーズにできるような気がする。
ソース
N = int(input()) # 紙を置く配列用のサイズ M = 1000 # 2次元配列(いもす法) A = [[0] * (M+2) for _ in range(M+2)] # 下記のようにする。 # 左上:-1、右上:+1 # 左下:+1、右下:-1 for i in range(N): lx, ly, rx, ry = [int(x) for x in input().split()] A[lx][ly] += 1 A[lx][ry] -= 1 A[rx][ly] -= 1 A[rx][ry] += 1 # 横向きに集計 for y in range(M+1): for x in range(M+1): A[x+1][y] += A[x][y] # 縦向きに集計 for x in range(M+1): for y in range(M+1): A[x][y+1] += A[x][y] # 各座標の枚数をカウントする ans = [0] * (N+1) for x in range(M+1): for y in range(M+1): ans[A[x][y]] += 1 # 結果の出力 for i in range(1, N+1): print(ans[i])
競プロ典型90問:027 - Sign Up Requests (★2)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_aa
挑戦結果
- 挑戦日:2021/10/07
- 結果:解けた
- 時間:3分
考えたこと
- setに入れて、チェックするだけ
公式解説
解説を読んだふりかえり
- 特になし。
ソース
N = int(input()) S = set() for i in range(N): s = input() if not s in S: S.add(s) print(i+1)
競プロ典型90問:026 - Independent Set on a Tree(★4)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_z
挑戦結果
- 挑戦日:2021/10/07
- 結果:解けた
- 時間:30分ぐらい
考えたこと
- 木なのでどこかのノードから距離を求めてしまえば求まりそう
- 距離0,2,4,6,・・・のノードは接続していない。
- 距離1,3,5,7,・・・のノードも接続してない。
- 距離が偶数 or 奇数のノードの集合で、数の多い方をN/2個並べればよい。
公式解説
解説を読んだふりかえり
- 自分の考えも間違ってはなかったけど、二部グラフの性質として、2色(赤/緑)に塗り分けるほうがシンプルと思った。
- 自分はbfsで実装したけど、2色で塗るdfsの実装のほうが遥かにシンプルだった。
- 解説をみた翌日、解説の方針で実装し直してみた。
- 再起の深さでREした。書きを追記した。
- sys.setrecursionlimit(1000000)
ソース
最初に提出したもの
from collections import deque N = int(input()) G = dict() # グラフ用 for i in range(1,N+1): G[i] = set() # インプットからグラフを作る for _ in range(N-1): a,b = [int(x) for x in input().split()] G[a].add(b) G[b].add(a) # 開始位置からの距離 D = {} # 展開予定 opened = deque() # すでに展開済み visited = set() # 開始位置 opened.append(1) D[1] = 0 while len(opened) > 0: c = opened.popleft() visited.add(c) for next in G[c]: if not next in visited: opened.append(next) D[next] = D[c]+1 # 距離が偶数同士はつながっていない、奇数同士はつながっていない # どちらか(数が多い方)をN//2個列挙すれば、隣り合わない頂点になっている。 L0 = [] L1 = [] for i in range(1,N+1): if D[i]%2==0: L0.append(i) else: L1.append(i) L = L0 if len(L0) >= len(L1) else L1 # 出力 print(*L[0:N//2])
解説をみてから作り直した
from collections import deque # 再起の深さを増やす import sys sys.setrecursionlimit(1000000) N = int(input()) G = dict() # グラフ用 for i in range(1,N+1): G[i] = set() # インプットからグラフを作る for _ in range(N-1): a,b = [int(x) for x in input().split()] G[a].add(b) G[b].add(a) # 木を1 or 0で塗る。(未探索の初期値は-1) C = [-1] * (N+1) # 深さ優先で再帰的に色を塗る def dfs(n, c): C[n] = c for next in G[n]: if C[next] == -1: dfs(next, 1-c) # 頂点1から色を塗る dfs(1,0) # 0で塗ったもの、1で塗ったもののうち、 # 個数が大きい方をN//2個表示すればOK ans0 =[] ans1 =[] for i, c in enumerate(C): if i>0: if c==0: ans0.append(i) else: ans1.append(i) ans = ans0 if len(ans0) >= len(ans1) else ans1 # 出力 print(*ans[:N//2])
競プロ典型90問:024 - Select +/- One(★2)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_x
挑戦結果
- 挑戦日:2021/10/06
- 結果:解けた
- 時間:5分
考えたこと
- 基本的に愚直に計算すれば良いと思った。
- 操作を行う数は、A[i]とB[i]の差
- これがK未満であればOKだけど、余ったら+/-を繰り返して消費しないといけないため、あまりは偶数でないとダメ。
公式解説
- 見つからなかった
解説を読んだふりかえり
- 見つからなかったのでなし。
ソース
N, K = [int(x) for x in input().split()] A = [int(x) for x in input().split()] B = [int(x) for x in input().split()] cnt = 0 for i in range(N): cnt += abs(A[i]-B[i]) ans = 'No' if cnt <= K: if (K-cnt)%2 == 0: ans = 'Yes' print(ans)
競プロ典型90問:022 - Cubic Cake(★2)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_v
挑戦結果
- 挑戦日:2021/10/06
- 結果:解けた
- 時間:30分ぐらい
考えたこと
- 一番小さい辺の長さで直方体を作る
- これが間違っていて、WAを出した
- 3辺の最小公倍数にカットすればよさそう
公式解説
解説を読んだふりかえり
- もっと早くに最小公倍数に気がつけばよかった
- 最小公倍数(gcd)は、python標準に含まれていて楽。
ソース
from math import gcd A,B,C = [int(x) for x in input().split()] d = gcd(A,B) d = gcd(d,C) ans = (A//d) + (B//d) + (C//d) - 3 print(ans)
競プロ典型90問:018 - Statue of Chokudai(★3)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_r
挑戦結果
- 結果:解けた
- 時間:40分ぐらい
考えたこと
- 俯角とはなにかを調べた
- 数式一発な問題と思った
- E869120 君の座標(x,y,z)の計算式を求めた
- 高橋直大像との俯角に必要な三角形を求めた
- 点1:高橋直大像 (X,Y,0)
- 点2:E869120君の座標 (eX, eY, eZ)
- 点3:E869120君をXY平面上に落とした場所 (eX, eY, 0)
- 辺の長さから角度を求めるために、atan2を使用した
公式解説
https://twitter.com/e869120/status/1384276005330690049/photo/1
解説を読んだふりかえり
- ただ三角関数と書いてあった。数式作るだけなので、もっと早くときたいところ。
- 3次元空間を脳内か紙面上で上手に描けないと駄目だな。
ソース
from math import sin, cos, pi, atan2, degrees, sqrt T = int(input()) L,X,Y = [int(x) for x in input().split()] Q = int(input()) E = [] for _ in range(Q): E.append(int(input())) # t秒時点のE869120君の座標 def xyz(t): x = 0 y = -L/2 * sin(2*pi*t/T) z = L/2 - L/2 * cos(2*pi*t/T) return x,y,z # t秒時点の答え def ans(t): eX,eY,eZ = xyz(t) return degrees(atan2(eZ, sqrt((X-eX)**2 + (Y-eY)**2))) # print(xyz(0)) # print(xyz(T/4)) # print(xyz(T/2)) # print(xyz(3*T/4)) for e in E: print(ans(e))
競プロ典型90問:016 - Minimum Coins(★3)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_p
挑戦結果
- 結果:できた
- 時間:5分ぐらい
考えたこと
- 三重ループで全列挙。ループのネスト条件をだんだん狭くするやつ。
- サンプル問題が帰ってこなかった。
- 最後は計算すればループが不要になることに気がついた
- とはいえサンプル問題をPythonで動かすと数秒かかる。pypyなら通るか?
公式解説
https://twitter.com/e869120/status/1383189464650981378
解説を読んだふりかえり
- 割とするっとはとけたけど、トライ&エラーが結構有った。最初から二重ループを思いつけると良かった。
ソース
N = int(input()) A,B,C = [int(x) for x in input().split()] cnt = 999999 for a in range(10000): for b in range(10000-a): if (N - (A*a + B*b)) % C == 0: c = (N - (A*a + B*b)) // C if c>=0: cnt = min(cnt, a+b+c) print(cnt)