名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。

CodeForcesのRound446のDiv2感想

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問題は解ける問題だったと思うので、惜しかったですね。相性が良いセットだったので、なおさら悔しいです。次回もまた、参加できるタイミングに頑張ります。


  1. お店じゃない集まりとかで余ったお酒を捨てる時にバケツがなくて、余った缶に集めてくとかありますよね

  2. 元の問題文から少し改変して書いています。なんで変えているのかというと、あまり綺麗でない言葉が使われているからです。(twitterで凍結されるやつね)気になる人はリンク先の問題文を読んでどうぞ。