CF、半年ぶりくらいに出ました。2完でした。 レーティングは1169 -> 1245(+76) と緑に綺麗に復帰できました。半年以上前に大失敗でレーティング300くらい溶かしているので、なんとかうまいセットに当たることを祈りつつ、地道にやっていきます。
これ思いつきなんだけど。コンテスト参加してGithubにどうせpushするので、感想用のmarkdown書いておけば、最悪ブログ書き忘れても感想思い出せそうなので、今後この運用もします。
今回はここに置きました。下記は転載。
https://github.com/yumechi/CodeForcesHandoutCodes/blob/master/Round446Div2/impression.md
簡単な感想
久々に2完出来たのでよかった。A, Bは制約に若干不安があったが、Pythonのまま通せた。 randomでシャッフルして少し重めのケースを試せたのは良かった。
C問題は1 1 1 1のパターンと、累積して答えを求めるパターンの計算を間違えていなければ通せていたので、惜しい所まで来ていた。
比較的得意なセットだったかもしれない。
1169 -> 1245(+76) と結構上がった。緑復帰嬉しい。
問題の紹介
A問題
Codeforces Round #446 (Div. 2) A. Greed
缶に残っている飲み物を2つの缶に収められるかどうか、という問題。1 飲み物の余っている量と、缶の最大容量が与えられます。
（容量が大きい缶の1番目と2番目の合計値) が （缶に余っている飲み物の総量）以上であれば、2つの缶に収まることは明確です。
言語：Python3
def solve(): n = int(input()) a = [int(i) for i in input().split()] b = [int(i) for i in input().split()] asum = sum(a) b.sort() print("YES" if b[-1] + b[-2] >= asum else "NO") if __name__=="__main__": solve()
B問題
Codeforces Round #446 (Div. 2) B. Wrath
一列に人が並んでいて、後ろの人が長さLiの爪を振りかざすと、その範囲にいる人が倒れます、立っている人は何人でしょう？という問題。2
これ結構悩んだんですが、ある地点に届く一番長い爪を記録しておいて、爪の範囲はインデックスを勧め、爪がないときだけ加算すると言うロジックで正解に持っていきました。もちろん一番後ろの人は必ず生き残るので、ちゃんと勘定しています。
例えば、こんな感じで記録しています。入力が下記のトキ
10 1 1 3 0 0 0 2 1 0 3
配列はこのように記録していました。
[-2, 0, 0, 0, -2, 0, -3, 0, 0, 0]
ここで前から見ていった時に、最初は-2だからインデックスを2だけ進めるけど、もしそれ以上の長さのものを途中で見つけてしまったらそっちに乗り換えてインデックスを更に進める…。というロジックで計算すると、奇跡的に答えが出ます。
もう少しきれいな方法がありそう。
言語：Python3
def solve(): n = int(input()) al = [int(i) for i in input().split()] cl = [0]*n for i in range(n - 1, -1, -1): if i - al[i] <= 0: cl[0] = min(cl[0], -i) else: cl[i - al[i]] = min(-al[i], cl[i - al[i]]) idx = 0 ans = 1 while idx < n - 1: if cl[idx] != 0: t = -cl[idx] while t > 0 and idx < n - 1: idx += 1 t -= 1 t = max(t, -cl[idx]) else: ans += 1 idx += 1 print(ans) if __name__=="__main__": solve()
C問題
Codeforces Round #446 (Div. 1) A. Pride
補足：Div.1のA問題がDiv.2のC問題となります。
隣り合う要素について、最大公約数を求めていき、全ての要素が1になるまでには何回かかりますか？という問題。
要素に1が含まれる場合は、配列の長さから1の数だけ引けば求まります。（これ忘れてHackされました）
それ以外の場合は、1をなるべく早く作るようにします。具体的には左から順番に最大公約数を求めていき、1になった時点で合計値が求まるので、それを更新していきます。（ここも最初変な計算方法をしていて、合計値を間違えていた）
これ本当は左からだけじゃなくて、右からも見たほうがいいような気がしたけど、どうなんでしょうね。。。
言語：Python3
def gcd(a, b): if a < b: a,b = b,a while b > 0: r = a % b a,b = b,r return a def solve(): n = int(input()) al = [int(i) for i in input().split()] if 1 in al: print(n - al.count(1)) return ans = -1 for i in range(n): t = al[i] for j in range(i + 1, n): t = gcd(t, al[j]) if t == 1: if ans == -1: ans = (j - i) + (n - 1) else: ans = min(ans, (j - i) + (n - 1)) print(ans) if __name__=="__main__": solve()
C問題は解ける問題だったと思うので、惜しかったですね。相性が良いセットだったので、なおさら悔しいです。次回もまた、参加できるタイミングに頑張ります。
