AtCoder Beginner Contest 128
A / Apple Pie
単位換算してやるだけ。
def solve(A: int, P: int): print(int((3*A+P)/2)) return
B / Guidebook
SとPを組み合わせて、昇順と降順にソートして(SP)、SPのもとの要素がどこにあったかを照らし合わせる。 この問題では複数の配列を組み合わせてソートする方法を学ぶことができた。
def solve(N: int, S: "List[str]", P: "List[int]"): # ソートのためにSPを合体 SP =[] for i in range(N): SP.append([S[i],P[i]]) # 都市名は昇順にし、同じ年の場合は降順でソートする t = sorted(SP, key=lambda x:(x[0],-x[1])) ans = [] for x in t: for j in range(N): x1,x2 = x if(x1 == S[j] and x2 == P[j]): ans.append(j+1) for i in ans: print(i) return
C / Switches
(on,off)の直積をN個で作って、全部を試す。 初心者ゆえ全探索をするのに組み合わせの「直積」という考え方を知ることができたのが一番の収穫。
def main(): N,M = map(int,input().split()) from collections import defaultdict d = defaultdict() for i in range(M): l = list(map(int,input().split())) d[i] = l[1:] p = list(map(int,input().split())) ans = 0 import itertools s = ('on', 'off') for i in itertools.product(s, repeat=N): anst = 0 for k,v in d.items(): if(len([x for x in v if(i[x-1] == 'on')])%2 == p[k]): anst += 1 if(anst == M): ans += 1 print(ans)
D / equeue
dfsかな???
E,F
AtCoder Beginner Contest 126
A / Changing a Character
Python なので指定された番号の文字をlower()するだけ。
def solve(N: int, K: int, S: str): sl = list(S) sl[K-1] = sl[K-1].lower() print(''.join(sl)) return
B / YYMM or MMYY
前半二文字と後半二文字で区切って、それぞれの部分で[1,12], 0 or [13,99]判定をする。
def solve(S: str): p1 = int(S[:2]) p2 = int(S[2:]) if(0 < p1 <= 12 and 0 < p2 <= 12): print('AMBIGUOUS') elif(0 < p1 <= 12 and (p2 == 0 or p2 > 12)): print('MMYY') elif((p1 == 0 or p1 > 12) and 0 < p2 <= 12): print('YYMM') else: print('NA') return
C / Dice and Coin
方針は、全部のサイコロの場合の確率を求めて、全部足しあげる。 1~Nまでのそれぞれのサイコロが出た場合の勝率は以下の通り。
def solve(N: int, K: int): ans = .0 for i in range(1,N+1): if(i <= K): t = math.ceil(math.log2(K/i)) ans += (1/N) * (1/2) ** t else: ans += 1/N print(ans) return
D / Even Relation
グラフが作れなくて終わり。
E / 1 or 2
Union-Find木は、自分ではちゃんと練習していたつもりでいたので、溶けなかったのはだいぶ悔しい。 この問題は、与えられる魔法を考慮したときに、「カードをめくる回数を一番少なくするにはどうしたらよいか?」を考える問題。 与えられるZは捨てて、XとYだけで、Union-Find木を構成すると、その連結成分が答え。
def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"): uf = UnionFind(N) for i in range(M): uf.union(X[i],Y[i]) # 連結成分の数が答え print(uf.num_graph()) return
F
ちょっと見てない
diverta 2019 Programming Contest
解答
A / Consecutive Integers
"連続した"値なのでN-(K-1)で良い。
B / RGB Boxes
全探索だが、3重ループは間に合いそうにないので、RとGは全部みて、Bは条件に合うか(非負であることとR,Gを使った残りを割り切れるか=(r,g,b)でちょうどNの組を作れるか)をチェックすればいける。
def solve(R: int, G: int, B: int, N: int): ans = 0 for i in range(0, N+1, R): for j in range(0, N+1, G): x = N - i - j if(0 <= x and x%B == 0): ans += 1 print(ans) return
参考(類題)
C / AB Substrings
追記)
下記の方針1について分岐が不足していたためWAだった。
ただ、WAのコードを見ると、共通部分と分岐先の計算の整理ができていなかったと思う。
解法としては、
- 共通部分として、max(0,x-1)とmin(a,b)を計算する。
- x >0 and (a > 0 or b > 0)の場合のみ+1する。(これはx > 1でaかbのどちらかが1以上であるとき、BxxA(カウントはx)の片方が'AB'になってくれるため)
↓@eijitさんに詳しく解説してもらった。
a と b が等しくて x が非ゼロの場合は xxA と Bxx の間に BA たちを挟み込んで + 1 になります。
— eijit (@eijit) 2019年5月11日
a と b が等しくなくて a か b のどちらかが非ゼロの場合は、余った方の xxA または Bxx と BA たちをつなげて + 1 になります。https://t.co/7GkmUDzLQj
の L.29-30 がこれらを合わせた計算です。
追記おわり)
ジャッジが詰まって、最後の結果はわからずACならずだったが、以下とった戦略である。
- 文字列をつなぐところで新しく'AB'になりうるのは「xxA」、「Bxx」、「BxxA」のみである。「xxA」と「Bxx」、「BxxA」はカウント-1で新規に’AB'を作れるので、それを数え上げる。
- すべての部分文字列でi.count('AC')
def solve(N: int, s: "List[str]"): x = 0; a = 0; b = 0 ans2 = 0 for i in s: ans2 += i.count('AB') if(i[0] == 'B' and i[-1] == 'A'): x += 1 elif(i[-1] == 'A'): a += 1 elif(i[0] == 'B'): b += 1 ##### AC2 #### ans1 = max(0,x-1) + min(a,b) if((a > 0 or b >0) and x > 0): ans1 += 1 print(ans1+ans2) return
D~F
わかんないわかんないわかんない
AtCoder Grand Contest 023 / A - Zero-Sum Ranges
解法
- 入力配列の累積和を作る(A(n) -> s(n+1))。
累積和の値について同じ値を集計する。※累積和のうちについてとなる区間は累積和が0になる。
(Pythonの場合) collectionsにあるCounterで累積和の同じ数を集計する。
(n個)の中で2個選ぶ組み合わせの総数を、すべての登場した数について数えあげる(個の中で個を選ぶ組み合わせは)
import sys from collections import Counter def solve(N: int, A: "List[int]"): s = [0]*(N+1) for i in range(N): s[i+1] = s[i] + A[i] # print(s[:10]) c = Counter(s) ans = 0 for k,v in c.items(): ans += v*(v-1)//2 print(ans) return
参考
解説AC @drkenさんの神解説
AtCoder Beginner Contest 084 / D - 2017-like Number
解法
- エラトステネスのふるいで、制約条件である100000までの素数表を作る (myo)
- 1で作成した素数表をもとに、2017に似た数 表を作る (r2017)
- r2017_ の累積和を取る (rodd)__
- Qのクエリに rodd[$ r_{i+1} $] - rodd[ $l_i$ ] で答えていく。
def eratos(n :int): # initialize isprime = [True] * (n+1) isprime[0] = isprime[1] = False for i in range(2, int(math.sqrt(n)+1)): if(isprime[i]): j = i+i while(j <= n): isprime[j] = False j = j+i return isprime def solve(Q: int, l: "List[int]", r: "List[int]"): myo = eratos(100000) rodd = [0]*100001 r2017 = [False]*100001 for i in range(1,100001): if(i%2 == 0): continue elif(myo[i] and myo[int((i+1)/2)]): r2017[i] = True for i in range(2,100001): rodd[i] = rodd[i-1] +(1 if r2017[i-1] else 0) ans = [0]*Q for i in range(Q): ans[i] = rodd[r[i]+1] - rodd[l[i]] for i in ans: print(i) return
参考
@drkenさんの神解説
AtCoder Beginner Contest 114 / C - 755
Reiwa一発目から解説ACで悔しい(ビクンビクン
方針は以下。
- 制約条件のため、1~Nの全件調査は間に合わない。
'753'のいずれかを含む値を 準753数 と定義して、これを全列挙する。
- 停止条件:sが入力Nに達すること
- 動作1:まず現在与えられている値の753数判定をする。
- 動作2:その後、その結果とは関係なく、今の桁数+1の753数を作ってdfs。
- 優勝
def dfs(s :str, n: int): if(int(s) > n): return 0 ret = 1 if all(s.count(c) for c in '753') else 0 for c in '753': ret += dfs(s+c, n) return ret def solve(N: int): # 0を入れないと、if(int(s) > n)で引掛かる print(dfs('0',N))
AtCoder Beginner Contest 017 - B - choku語
pythonで文字列を置換していくような場合はstr.replace()が便利
def solve(X: str): ans = X.replace("ch", "").replace("o", "").replace("k", "").replace("u", "") print(YES) if not ans else print(NO) return