ABC124(3完)
ハロートナミです。
ABC124やりました。3完太郎なので3完でした
ネタバレがあります。
A
考え
(AとBのでかい方) + (でかい方から-1した数字とでかくない方のうちのでかい方)
書いたソース
A,B = map(int, input().split()) if A > B: print(max(A,B) + max(A-1,B)) else: print(max(A,B) + max(A,B-1))
なんだけど、今思えば
A,B = map(int, input().split()) print(max(A,B)+ max(max(A,B)-1, min(A,B))
これの方が考えに近いですね。こう書いたら20秒ぐらい早くなってた気がする。はい
B
問題文が難しかった
考え
各Hに関して、より左にあるH全てを確認して条件を満たすやつを数えるだけ。
書いたソース
N = int(input()) hList = [int(x) for x in input().split()] count = 0 for i,h in enumerate(hList): ng = False for j in range(i+1): if hList[j] > h: ng = True break if ng == False: count += 1 print(count)
もうちょっとなんとかならなかったの感凄い。
C
考え
どの隣り合う 2 枚のタイルも異なる色にする、には
白黒白黒……の並びにするか、黒白黒白……の並びにするかの2択しかない。
条件的にいけそうなので両方のパターン計算して小さい方出力する。
書いたソース
S = input() #01010... bw = 0 for i in range(len(S)): if i % 2 == 0: if S[i] == '1': bw += 1 else: if S[i] == '0': bw += 1 #10101... wb = 0 for i in range(len(S)): if i % 2 == 0: if S[i] == '0': wb += 1 else: if S[i] == '1': wb += 1 print(min(bw,wb))
ソースだけ見ると長ったらしいんだけど片方書いたらコピペして微修正するだけなのですぐ。
コメントまで書いた割にbwとwbの意味が逆かもしれない。脳が良くないのでどっちが黒でどっちが白か分からん
D
なんと今回はCを解くまで9分21秒でした。
その後最後の最後までDに着手したので90分以上使って解けなかったことになります。
考え
1と0の切り替わるポイントを列挙してKに応じて全パターンを計算する。
書いたソース
クソなので読まなくていいです(載せる意味もないです)
N, K = map(int, input().split()) S = input() change = [0] for i in range(1,N): if S[i] == '1' and S[i-1] != '1': change.append(i) elif S[i] == '0' and S[i-1] != '0': change.append(i) if S[0] == '1': if K >= len(change)//2: print(N) quit() else: if K >= (len(change)+1)//2: print(N) quit() result = 0 if S[0] == '1': for i, point in enumerate(change): if i + K*2 + 2 > len(change): if i % 2 == 0: if result < N - point: result = N - point else: if result < N - point - 1: result = N - point - 1 break if i % 2 == 0: if result < change[i + 1 + K*2] - point: result = change[i + 1 + K*2] - point else: if result < change[i + K*2] - change[i-1]: result = change[i + K*2] - change[i-1] else: for i, point in enumerate(change): if i + K*2 + 2 > len(change): if i % 2 == 0: if result < N - point - 1: result = N - point - 1 else: if result < N - point: result = N - point break if i % 2 == 0: if i == 0: if result < change[i + K*2] - change[i]: result = change[i + K*2] - change[i] continue if result < change[i + K*2] - change[i-1]: result = change[i + K*2] - change[i-1] else: if result < change[i + 1 + K*2] - point: result = change[i + 1 + K*2] - point print(result)
これでWA2個が消せずにタイムアップでした。クソクソ
今回のDは解説に載ってた発想は出来てたのに、"今確認中の要素が0か1か"を判断する方法がクソになって終わりでした。
S[i]見りゃいいだけのところを"S[0]が1ならn回目の反転後の要素は…"みたいな発想をしたせいでソースが複雑になり、実装力不足によって多分どっかにバグを埋め込んでしまって終了です。バカだなあ。
教訓として複雑なソースは容易に人間の限界を超えてバグ潰しの出来ない領域まで飛んでいくという事です。
未だにどこがバグってるかよく分からないし、こんなの読みたくもない。悲しいね
ブログ書き終わったら単純なソースでは通ったのかどうか検証します。
追記:
S[i]が1の場合と0の場合で場合分けするように単純に書いたら通りました。複雑さは悪
結果
Cまでの早解きが効いてて何とか1000以上のパフォーマンスになりました。
レートは微増です。微増が多すぎて今月中に1000超えたらいいなになっています。おわり