競プロ典型 90 問：072 - Loop Railway Plan（★4）
問題
挑戦結果
- 挑戦日：2021/10/30
- 結果：解けた
- 時間：45分ぐらい
考えたこと
- 効率的な解法は特に思いつかないし、制約が小さいので全探索か？
- 再帰で全ルートを求める
公式解説
https://twitter.com/e869120/status/1407109731546636289/photo/1
解説を読んだふりかえり
- ちょっと時間はかかったけど、ACできてよかった。
- ビットDPは後で調べよう。(https://atcoder.jp/contests/typical90/tasks/typical90_as が参照されてるけど★6なので保留)
ソース
H,W = [int(x) for x in input().split()] C = [] for _ in range(H): L = input() C.append(L) # pathの末尾からスタートして、長さを返す def f(path): # x,yが末尾(現在の座標) x,y = path[-1] dX = [0, 0,1,-1] dY = [1,-1,0, 0] ans = -1 # 隣に進む for dx,dy in zip(dX,dY): # 進んだ座標 X = x+dx Y = y+dy # 枠内＆平地ならすすめる if (0<=X<W) and (0<=Y<H) and C[Y][X]==".": # まだ通ってない場合は進んで再帰 if not (X,Y) in path: path.append((X,Y)) ans = max(ans, f(path)) path.pop() # 開始位置に戻れる場合もスコア更新 if (X,Y) == path[0] and len(path)>=4: ans = max(ans, len(path)) # print(path) return ans ans = -1 # 開始地点は全箇所 for x in range(W): for y in range(H): if C[y][x] == ".": path = [(x,y)] ans = max(ans, f(path)) print(ans)
競プロ典型 90 問：070 - Plant Planning（★4）
問題
https://atcoder.jp/contests/typical90/tasks/typical90_br
挑戦結果
- 挑戦日：2021/10/29
- 結果：解けた
- 時間：10分
考えたこと
公式解説
https://twitter.com/e869120/status/1406020809492090882
解説を読んだふりかえり
- 珍しく、考察も実装もするっといった。
- 中央値で絶対値最小となるテクニックは重要らしい。
ソース
N = int(input()) X,Y = [],[] for _ in range(N): x,y = [int(x) for x in input().split()] X.append(x) Y.append(y) # XとYについては、独立して考えてOK。 # 発電所の左側と右側の工場の数が等しい場合が最短になる # ソートして真ん中にある工場の場所を採用すればOK X.sort() Y.sort() m = N//2 # 発電所の場所はX[m],Y[m]。そこからの距離を求める XX = [abs(X[i] - X[m]) for i in range(N)] YY = [abs(Y[i] - Y[m]) for i in range(N)] ans = sum(XX) + sum(YY) print(ans)
競プロ典型 90 問：069 - Colorful Blocks 2（★3）
問題
挑戦結果
- 挑戦日：2021/10/29
- 結果：解けた
- 時間：15分
考えたこと
- 1ブロック目：Kパターン、 2ブロック目：K-1パターン、 3ブロック目以降：K-2パターン なので、これをかければ良い。modを取れば大きな数字ならないので、速度面も問題ないはず。
- 実装したらTLEだった。
- ループがN回(N乗)だけど、Nは
と大きかったことに気がついた。
を N回のループの計算するのではなく、
→二乗→
→二乗→
とやって、logNの計算量で求めるやつだなと思ったけど、Pythonにはライブラリ化されていた気がしたので、ググった。
- pow(x,y,z) で、
をzであまりをとった値になることがわかったので、これに変更してAC。
公式解説
https://twitter.com/e869120/status/1405659999179722754
解説を読んだふりかえり
- 繰り返し二乗法
- powを使ったけど、自分でも実装できるようになったほうが良いのかもしれない。
ソース
N, K = [int(x) for x in input().split()] MOD = 10**9 + 7 if N>=2: ans = K * (K-1) * pow(K-2, N-2, MOD) ans %= MOD elif N==1: ans = K print(ans)
競プロ典型 90 問：067 - Base 8 to 9（★2）
問題
挑戦結果
- 挑戦日：2021/10/28
- 結果：解けた
- 時間：20分
考えたこと
- 再現するだけ。
- いったん10進法に戻して計算する。
- コーナーケース(0のとき)で、WAを出した
- 実装はちょっと汚い気がした。
公式解説
https://twitter.com/e869120/status/1404931743820357633
解説を読んだふりかえり
- N=0のコーナーケースに注意と記載されていて凹んだ
ソース
N, K = input().split() K = int(K) # 操作。Sは文字列。 def sousa(S): if int(S) == 0: return "0" d = 1 # Sを9進法で解釈した数値がnum9。(num9は10進数) num9 = 0 for c in reversed(S): num9 += (d * int(c)) d *= 8 # num9(数値)を、文字列(9進法)に変える str9 = [] while num9 != 0: str9.append(str(num9%9)) num9 //= 9 str9.reverse() # 文字列にして、8を5に変える str9 = "".join(str9) return str9.replace("8","5") for _ in range(K): N = sousa(N) print(N)
競プロ典型 90 問：064 - Uplift（★3）
問題
挑戦結果
- 挑戦日：2021/10/27
- 結果：解けた
- 時間：1時間ぐらい
考えたこと
- 各区画の標高を持つのはTLE。
- 各クエリ時点での不便さを更新していくようなアルゴリズムでないと、計算量的に間に合わなそう
- 左隣の標高との差を保持するのが良いかも。標高差を
とすると、
を合計すれば答えになる。
- ただし、それだと各クエリで
かかると、TLEするので、なにか工夫が必要そう。
- 最初に不便さを求めておけば、各クエリでの更新されるのは2箇所だけなので、その部分について不便さの差分を計算できそう。
公式解説
https://twitter.com/e869120/status/1403483256234799105/photo/1
解説を読んだふりかえり
- 考え方はあっていたので良かった。こういうのは階差と呼ぶらしい。
- もう少し早く検討、実装ができたら良かったなぁ。。。
- 解けたけど、時間を置いてもう一度解いてみようかな。
ソース
N, Q = [int(x) for x in input().split()] A = [int(x) for x in input().split()] L,R,V = [],[],[] for _ in range(Q): l,r,v = [int(x) for x in input().split()] L.append(l-1) R.append(r-1) V.append(v) # 左との差分(差分を更新していく) D = [0] * N for i in range(1, N): D[i] = A[i] - A[i-1] # 現在のスコア(不便さ) score = 0 for i in range(N-1): score += abs(A[i] - A[i+1]) # 各クエリの計算 for i in range(Q): # lからrがv増えるので、差分としては下記の2箇所が変更される # D[l] ・・・・[l-1]と[l]の差 # D[r+1] ・・・[r]と[r+1]の差 l,r,v = L[i], R[i], V[i] if l!=0: # 変更前の差分をのぞいて、変更後の差分を加える score -= abs(D[l]) D[l] += v score += abs(D[l]) if r+1<N: # 変更前の差分をのぞいて、変更後の差分を加える score -= abs(D[r+1]) D[r+1] -=v score += abs(D[r+1]) print(score)
063 - Monochromatic Subgrid（★4）
問題
挑戦結果
- 挑戦日：2021/10/26
- 結果：解けた
- 時間： 1時間ぐらい
考えたこと
- DPとかを使うのかと思ったけど、 愚直にやればできそうな気がした。
- 8行分のどれを使うかは全パターン列挙しても256通り。
- 選択した行について、列が同じ数字になっているものを数えれば良さそう
公式解説
https://twitter.com/e869120/status/1403121388773249024/photo/1
解説を読んだふりかえり
- 変な制約、状態数が少ないものは全探索というのが定石なもよう。
- その点には気がつけた気がする。
- 実装が遅かったり、計算量見積もりが適当だったのは良くなかった。
ソース
import itertools # from collections import defaultdict from collections import Counter H, W = [int(x) for x in input().split()] P = [] for _ in range(H): l = [int(x) for x in input().split()] P.append(l) ans = 0 for i in range(1<<H): # Pから行を抜粋したのがP2 ci = [1 if i&(1<<j) else 0 for j in range(H)] P2 = list(itertools.compress(P, ci)) # P2の列を順番に各列みて、すべて同じ数値であるかを求める counter = Counter() for c in range(W): L = [P2[r][c] for r in range(len(P2))] S = set(L) if len(S)==1: n = S.pop() counter.update([n]) # 同じ数値の場合は、面積を求めてみて、更新できればする if len(counter.most_common()) != 0: v, cnt = counter.most_common()[0] ans = max(ans, cnt * len(P2)) print(ans)
競プロ典型 90 問：061 - Deck（★2）
問題
挑戦結果
- 挑戦日：2021/10/26
- 結果：解けた
- 時間：5分
考えたこと
- listだと先頭に入れるのが遅いのでダメ。
- dequeを使えば実装するだけ。
公式解説
https://twitter.com/e869120/status/1402395219287371779
解説を読んだふりかえり
- deque を知っていますか？ とのこと。知っていてよかった。
ソース
from collections import deque queue = deque() Q = int(input()) for _ in range(Q): t,x = [int(x) for x in input().split()] if t==1: # 山の一番上に入れる queue.appendleft(x) elif t==2: # 山の一番下に入れる queue.append(x) elif t==3: # x番目のカード ans = queue[x-1] print(ans)
