競プロ典型 90 問：058 - Original Calculator（★4）
問題
挑戦結果
- 挑戦日：2021/10/25
- 結果：解けた (でも、2,3問WAが出てデバッグに苦労した)
- 時間：1時間ぐらい
考えたこと
- ボタンAを押していく中で、過去に登場した数値が出てきたらあとは同じ。周期性を使って計算すれば良さそう。
公式解説
https://twitter.com/e869120/status/1400947432440008704
解説を読んだふりかえり
- 特に問題なかった。
- 2,3ケースだけWAが出ていて、40分ぐらいたったところで回答みた。方針はいいけど、単純に実装力の問題だった・・・。ソースや条件を整理し直してAC。
ソース
N, K = [int(x) for x in input().split()] # ボタンAの操作の数字 def next(x): x2 = x y = 0 while x2 != 0: y += (x2 % 10) x2 //= 10 return (x + y) % (10**5) # ループ検知のためのすでに登場した数値華道家のメモ memo = [False] * (10**5 + 1) # 登場した数値を保持 numlist = [] # ボタンAをK回押す。ただし、ループ検知したら抜ける。 x = N for i in range(K+1): numlist.append(x) memo[x] = True x = next(x) # すでにある場合 if memo[x]: break if i<K: # breakで抜けてきたとき st_idx = numlist.index(x) # Wが周期 W = len(numlist) - st_idx idx = (K - st_idx) % W ans = numlist[st_idx + idx] else: # 周期性が無いときは、末尾でOK ans = numlist[-1] print(ans)
競プロ典型 90 問：055 - Select 5（★2）
問題
挑戦結果
- 挑戦日：2021/10/21
- 結果：解けなかった(TLE)
- 時間：30分
考えたこと
- コンビネーションで全列挙は簡単にかけるけど、
ぐらいになって、TLEしそう。
- でも高速な解法は思いつかないので、全列挙してみよう。TLEした。
- 解けなかった。
公式解説
https://twitter.com/e869120/status/1399859200046505984/photo/1
解説を読んだふりかえり
- まさかの全列挙で良かった。まぁ、★２だもんなぁ。
=
はOKらしい。
- 結局の所、自分の遅いところも解説に書いてあって、計算途中で巨大なintになると遅いということだった。
- %P を入れまくったら通った。あとコンビネーションよりも、ループで列挙したほうが早かった。
ソース
コンビネーションバージョン(2.7s)
from itertools import combinations N,P,Q = [int(x) for x in input().split()] A = [int(x) for x in input().split()] combs = combinations(A,5) ans = 0 for C in combs: if (C[0]*C[1]%P*C[2]%P*C[3]%P*C[4]%P) == Q: ans += 1 print(ans)
ループバージョン(0.9s)
N,P,Q = [int(x) for x in input().split()] A = [int(x) for x in input().split()] ans = 0 for a in range(N): for b in range(a+1, N): for c in range(b+1, N): for d in range(c+1, N): for e in range(d+1, N): if A[a] * A[b]%P * A[c]%P * A[d]%P * A[e]%P == Q: ans += 1 print(ans)
競プロ典型 90 問：052 - Dice Product（★3）
問題
挑戦結果
- 挑戦日：2021/10/21
- 結果：解けた
- 時間：15分
考えたこと
- サイコロ２個の事例で計算してみていると、各サイコロの和をとって、それを掛けていけばOKと気がついた
公式解説
https://twitter.com/e869120/status/1398409831044632576
解説を読んだふりかえり
*「複雑な問題で小さいケースを考えるのは重要」とのこと。それをやっていたので良かった。 * ただ、もっとスパッと分かるようになりたい気もする。
ソース
N = int(input()) ans = 1 MOD = 10**9 + 7 for n in range(N): A = [int(x) for x in input().split()] sa = sum(A) ans *= sa ans %= MOD print(ans)
競プロ典型 90 問：050 - Stair Jump（★3）
問題
挑戦結果
- 挑戦日：2021/10/17
- 結果：解けた
- 時間：10分
考えたこと
- いかにもDP
- DP[n]をn段目にたどり着く方法とおいて、DP[n] から DP[n+1]とDP[n+L]に配ればOK。
- 最初、1段～L段上にすすめると勘違いしていたけど、そうではなくて1段orL段だった。
公式解説
https://twitter.com/e869120/status/1397684795560259586
解説を読んだふりかえり
- 特に問題はないけど、解説はもらうDPっぽい考え方になってると思った。どっちでも良いんだろうけど。
ソース
N,L = [int(x) for x in input().split()] DP = [0] * 1000000 DP[0] = 1 MOD = 10**9 + 7 for i in range(N+1): DP[i+1] += DP[i] DP[i+1] %= MOD DP[i+L] += DP[i] DP[i+L] %= MOD print(DP[N])
再帰でもやってみた
- 解けた
- 自分の環境(Win, Python3.9)では、大きいサイズの問題のときに無言で終了する症状が再発。
- 下記のときと全く同じ
- ebinafactory.hatenablog.com
- AtCoder上では問題ないようで無事にAC。速度面は下記。
- Python3：163ms
- PyPy3：772ms
- PyPy3(DP版)：69ms
- Python環境でのDP or メモ化再帰については、
from functools import lru_cache import sys sys.setrecursionlimit(1000000) N,L = [int(x) for x in input().split()] MOD = 10**9 + 7 @lru_cache(maxsize=1000000) def f(n): if n==0: return 1 elif n<0: return 0 return (f(n-1) + f(n-L))%MOD print(f(N))
競プロ典型 90 問：048 - I will not drop out（★3）
問題
挑戦結果
- 挑戦日：2021/10/17
- 結果：解けた
- 時間：20分ぐらい
考えたこと
- 各秒で貪欲に点数が一番多い問題(部分点 or 満点狙い)に取り組むのが良い。それを上手に実装すればよさそう。
- 部分点は最初にソートしておいて、上から順に取り出していけばいいけど、満点狙いはそうもいかなそう。
- pythonだとheapq(優先度付きキュー)を使えば良さそう
公式解説
https://twitter.com/e869120/status/1396960059796582400/photo/1
解説を読んだふりかえり
- heapq使わなくても良さそうだった。あと、自分の実装のHQ1はheapqにする必要はまったくなかった。
- ソートして上からK個の合計で良かったのか。
から、満点狙いをする場合(
の点数を取りに行く場合)には、対応する部分点は必ず取れていて、これに気がついていたら実装がすごく簡単になる。自分はこれに気がつけていなかった・・・。
ソース
import heapq N, K = [int(x) for x in input().split()] A,B = [],[] HQ1,HQ2 = [],[] for i in range(N): a,b = [int(x) for x in input().split()] A.append(a) B.append(b) # (部分点, 最高点までの差分)を優先度キューに入れる。(※最大化が欲しいので-にする) HQ1.append((-b,-(a-b))) heapq.heapify(HQ1) score = 0 for _ in range(K): # 部分点 or 最高点の大きい方を求める(-つける) s1 = -9999 if len(HQ1)==0 else -HQ1[0][0] s2 = -9999 if len(HQ2)==0 else -HQ2[0] # 部分点のほうが大きい場合 if s1>s2: x,y = heapq.heappop(HQ1) score += (-x) # 満点用の優先度キューに追加 heapq.heappush(HQ2,y) # 満点を狙ったほうがいい場合 else: x = heapq.heappop(HQ2) score += (-x) print(score)
解説読んだあと
import heapq N, K = [int(x) for x in input().split()] S = [] for i in range(N): a,b = [int(x) for x in input().split()] S.append(b) S.append(a-b) S.sort(reverse=True) print(sum(S[:K]))
競プロ典型 90 問：https://atcoder.jp/contests/typical90/tasks/typical90_at
問題
挑戦結果
- 挑戦日：2021/10/17
- 結果：解けた
- 時間：10分
考えたこと
- 愚直に全パターンやると、
なのでTLE。
- 46の倍数だけを考えるので、mod 46だけを考えれば良さそう。
- たとえば、Aが[0,1,2,46, 92]とかだったら、0が3個、1が1個、2が1個のようにまとめてしまって良さそう。
- A,B,Cそれぞれで、mod 46での個数を数えたら、46の倍数になるものを全パターン求めても
でぜんぜんOK。
公式解説
https://twitter.com/e869120/status/1395873457259225091
解説を読んだふりかえり
- 自分の理解と同じっぽいのでOK。
ソース
N = int(input()) A = [int(x) for x in input().split()] B = [int(x) for x in input().split()] C = [int(x) for x in input().split()] AA = [0] * 46 BB = [0] * 46 CC = [0] * 46 for i in range(N): AA[A[i]%46] += 1 BB[B[i]%46] += 1 CC[C[i]%46] += 1 ans = 0 for i in range(46): for j in range(46): for k in range(46): if(i+j+k) % 46==0: ans += (AA[i] * BB[j] * CC[k]) print(ans)
競プロ典型 90 問：044 - Shift and Swapping（★3）
問題
挑戦結果
- 挑戦日：2021/10/17
- 結果：解けた
- 時間：10分
考えたこと
- T1とT3はやるだけ。
- T2は右シフトを愚直に実装するとTLEしそう。
なので、シフトに
、クエリ数が
だと
でまずそう。
- シフトの代わりに基準にする場所を持っておいて、T2のときに基準をずらせば良さそう。T1とT3はその基準からの相対位置でやる。
公式解説
https://twitter.com/e869120/status/1395148057730187265
解説を読んだふりかえり
- 特に問題なかった
ソース
N,Q = [int(x) for x in input().split()] A = [int(x) for x in input().split()] # シフトは重いので、代わりに基準の場所を決めておく d = 0 for _ in range(Q): T,x,y = [int(x) for x in input().split()] # 基準と0-indexの調整 x = (x -1 + d) % N y = (y -1 + d) % N if T==1: # 入れ替える A[x], A[y] = A[y], A[x] elif T==2: # シフトの代わりに基準をずらす d+=(N-1) elif T==3: print(A[x])
