競プロ典型90問:014 - We Used to Sing a Song Together(★3)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_n
挑戦結果
- 結果:できた
- 時間:3分
考えたこと
- 小学生も学校も、左から順番にペアを組むのが最短になりそうと思った
公式解説
https://twitter.com/e869120/status/1382478816627478530/photo/1
解説を読んだふりかえり
- なんとなく正しそうという状態で解いてしまったが、証明を読んで見ればそうかと思った。
ソース
N = int(input()) A = [int(x) for x in input().split()] B = [int(x) for x in input().split()] A.sort() B.sort() sum = 0 for i in range(N): sum += abs(A[i] - B[i]) print(sum)
競プロ典型90問:012 - Red Painting(★4)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_l
挑戦結果
- 結果:できなかった
- 時間:30分ぐらい
考えたこと
- 囲碁っぽくやること。TLEした・・・。
公式解説
- UnionFindを思い出したし、以前にライブラリ化もしていた。
解説を読んだふりかえり
- UnionFindでやったらサクッとできた。
- ただし、UnionFindの高速化はやってないので、どこかで対応したほうが良さそう。
ソース
H, W = [int(x) for x in input().split()] Q = int(input()) ############################################ # Union Find # N = 100 N = (H+2) * (W+2) PARENT = list(range(N)) def root(n): if PARENT[n] == n: return n else: ret = root(PARENT[n]) PARENT[n] = ret return ret def same(n1, n2): return root(n1) == root(n2) def unite(n1, n2): n1 = root(n1) n2 = root(n2) if n1 == n2: return PARENT[n1] = n2 ############################################ # 盤面が赤になっているか B = [False] * N # 2次元を1次元に変換 def rc2p(r,c): return (W+2)*r + c # 1のクエリ(色を塗る) def query1(r,c): pU = rc2p(r+1,c) pD = rc2p(r-1,c) pR = rc2p(r,c+1) pL = rc2p(r,c-1) p = rc2p(r,c) B[p] = True if B[pU]: unite(p,pU) if B[pD]: unite(p,pD) if B[pR]: unite(p,pR) if B[pL]: unite(p,pL) # 2のクエリ(判定) def query2(r1,c1, r2,c2): ans = "No" p1 = rc2p(r1,c1) p2 = rc2p(r2,c2) if same(p1,p2) and B[p1] and B[p2]: ans = "Yes" print(ans) # メイン部分 for _ in range(Q): q = input().split() if q[0]=="1": query1(int(q[1]), int(q[2])) else: query2(int(q[1]), int(q[2]),int(q[3]), int(q[4]))
競プロ典型90問:010 - Score Sum Queries(★2)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_j?lang=ja
挑戦結果
- 結果:解けた
- 時間:20分ぐらい
考えたこと
- 愚直は計算量がNGなんだろうと思った。累積和なことは思いついた。
- クラスがあるからどう扱えばいいかと思ったけど、それぞれ累積和を持てば良さそう気がついた
公式解説
https://twitter.com/e869120/status/1380652465834532865
解説を読んだふりかえり
- 特になし。★2なのでサクッとときたい。
ソース
N = int(input()) C, P = [], [] for _ in range(N): c, p = [int(x) for x in input().split()] C.append(c) P.append(p) Q = int(input()) L, R = [], [] for _ in range(Q): l, r = [int(x) for x in input().split()] L.append(l) R.append(r) # 累積和をクラス別に計算する ruiseki1 = [0] * (N+1) ruiseki2 = [0] * (N+1) for i in range(N): ruiseki1[i+1] = ruiseki1[i] + (P[i] if C[i]==1 else 0) ruiseki2[i+1] = ruiseki2[i] + (P[i] if C[i]==2 else 0) # print(ruiseki1) # print(ruiseki2) for i in range(Q): l, r = L[i], R[i] ans1 = ruiseki1[r] - ruiseki1[l-1] ans2 = ruiseki2[r] - ruiseki2[l-1] print(f"{ans1} {ans2}")
競プロ典型90問:008 - AtCounter(★4)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_h
挑戦結果
- 結果:解けた
- 時間:30分ぐらい
考えたこと
- DPっぽいことは最初から感じた
- 遷移の条件に苦労した
公式解説
https://twitter.com/e869120/status/1379927227739987972?s=20
解説を読んだふりかえり
- DPの作り方は解説と同じで良かった。少しDPに慣れてきたか。
- ただ、時間もかかったし、理解度がまだ足りてない感じはする。
ソース
N = int(input()) S = input() MOD = 10**9 + 7 # 先頭に足して1-originにする。末尾も範囲チェックを楽にする都合で追加 ATCODER = "_atcoder_" S = "@" + S + "@" # DPテーブルは大きめに確保 # dp[i][j]のとき、 # Sのi文字目まで使用していて、"atcoder"のj文字目までカバーしているパターン数 dp = [[0] * (len(ATCODER)+10) for _ in range(N+10)] # Sを0文字目まで使っていて、"atcoder"の0文字目までカバーしているのが1パターン。 dp[0][0] = 1 # 配るDP for i in range(N+1): for j in range(7+1): # 遷移①:使える文字数が増えても、既存パターン数はOK dp[i+1][j] += dp[i][j] dp[i+1][j] %= MOD # 遷移②:使える文字が増えて、atcoderの次の文字とマッチする場合 if ATCODER[j+1] == S[i+1]: dp[i+1][j+1] += dp[i][j] dp[i+1][j+1] %= MOD print(dp[N][7])
競プロ典型90問:007 - CP Classes(★3)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_g
挑戦結果
- 結果:解けた
- 時間:10分ぐらい
考えたこと
- 愚直はTLEする
- $A$はソートすれば二分探索で近いクラスを見つけられる。見つけたら前後のどちらか($A_i$と$A_{i+1}$)が最も近いクラスなので、それの近い方のクラスに入れればOK。
公式解説
https://twitter.com/e869120/status/1379565222541680644
解説を読んだふりかえり
- スルッと解けたので、特になし。
ソース
import bisect # インプット N = int(input()) A = [int(x) for x in input().split()] Q = int(input()) B = [int(input()) for _ in range(Q)] # 二分探索(bisect)用にソートしておく A.sort() INF = float('inf') for bval in B: diff = INF # A[aidx] <= bval < A[aidx+1] を二分探索で探すので、近い方を選択採用すればOK aidx = bisect.bisect_left(A, bval)-1 diff = abs(A[aidx] - bval) if aidx+1 < len(A): diff = min(diff, abs(A[aidx+1] - bval)) print(diff)
競プロ典型90問:006 - Smallest Subsequence(★5)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_f
挑戦結果
- 結果:できなかった
- 時間:30分ぐらい
考えたこと
- 全列挙を再帰的に作ることはできると思ったけど、計算量的にどう考えても無理だった。
- 貪欲に求める方法も考えたけど、思いつかなかった。
解説を読んだふりかえり
- 貪欲な方法を思いつかなかったし、その上、事前計算が必要だったようで無理だった。
- なんかもう一度解いても解ける気がしてないけど、辞書式最小は前から貪欲法は覚えておこう
公式解説
https://twitter.com/e869120/status/1379202843622576130?s=20
ソース
from string import ascii_lowercase N,K = [int(x) for x in input().split()] S = input() INF = float('inf') # 事前の計算用のテーブル C = [[INF] * N for _ in range(len(ascii_lowercase))] L = [INF] * len(ascii_lowercase) # 後ろから、文字がある場所を計算 for i,ch in reversed(list(enumerate(S))): L[ord(ch)-ord('a')] = i for a in ascii_lowercase: aidx = ord(a)-ord('a') C[aidx][i] = L[aidx] ans = "" idx = 0 # Sのidx文字目を候補にするかどうか # 一番若い文字をピックアップできるかどうかは、ピックアップした後続に文字数があればOK while (idx < N and len(ans)<K): for j,ch in enumerate(ascii_lowercase): if N-C[j][idx] >= K-len(ans): ans += ch idx = C[j][idx] # print(ans) break idx+=1 print(ans)
競プロ典型90問:004 - Cross Sum(★2)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_d
挑戦結果
- 結果:解けた
- 時間:15分ぐらい
考えたこと
- 愚直に計算するとTLEなんだろうと思った
- 事前に縦と横で集計しておくと、$縦合計+横合計-A[i][j]$ で$B[i][j]$が求まると気がついた
解説を読んだふりかえり
- デバッグで思ったより時間がかかってしまった
- 愚直にやった場合の計算量も計算してみようと思った。
ソース
H, W = [int(x) for x in input().split()] A = [[int(x) for x in input().split()] for _ in range(H)] # 縦と横の合計 sumH = [0] * W sumW = [0] * H # 横についての合計 for i in range(H): for j in range(W): sumW[i] += A[i][j] # 縦についての合計 for j in range(W): for i in range(H): sumH[j] += A[i][j] # 縦方向の合計+横方向の合計 - A[i][j] for i in range(H): L = [] for j in range(W): L.append(str(sumH[j] + sumW[i] - A[i][j])) print(" ".join(L))