yukicoder contest 155

yukicoderは練習で何度か利用してましたが、コンテストは初でした
結果は3完でした

A. No.476 正しくない平均

問題文はこちら
No.476 正しくない平均 - yukicoder

感想

実際に計算で求めた平均とaが一致すればよいかみればよい
……ってやったんですけど、n * aがsum(x)に一致するかどうかを
見る方がスマートだし少数扱わなくていいしでいいなあって思いました
細かいとこですけど、そういうとこにぱっと気づけるようになりたい
計算量はsum(x)を求めるためのO(n)

実際に書いたコード

n, a = map(int, input().split())

x = [int(i) for i in input().split()]
ave = sum(x) / n

if a == ave:
    ans = 'YES'
else:
    ans = 'NO'

print(ans)

B. No.477 MVP

問題文はこちら
No.477 MVP - yukicoder

感想

最初N/(K + 1)の切り上げかなと思ってそれで出したんですがWAしました
よく考えたらこれだとN / (K + 1)がちょうど割りきれるときに不確定になってしまうということに気づきました
例えば、N = 18, K = 2だと6になりますが、6,6,6だと抽選ですね
ってことで結局N//(K+1) + 1にして正解になりました
計算量はO(1)ですね

感覚的に解いたんですが実際にこれが正しいことを証明するってなると困りますね
どうすればいいんですかね
問題文には何人救援が来るか明示されてないですが、たぶん救援がK人来たときに
自分含めK + 1人のなかでK + 1位になってしまわないようにすればいいですね
それで、N//(K+1)以下にすると他のK人がN//(K+1)ダメージ以上出せてしまうのでダメ
N//(K+1)+1にすると、最低でも一人N//(K+1)+1未満のダメージしか出せない人間が出るので、K位以上になれることが確定する
よってここがMVPもらえる最小限のダメージ、って感じですかね

関係無いですが切り上げを求めるときにceil(a/b)使うと今回みたいに
a = 1000000000000000000, b = 3 とかだと精度が足りなくてちゃんとした答えにならないんですね
手元で計算するとceil(a/b) = 333333333333333312になってしまいました
(a + b - 1) // b で切り上げは計算したほうがいいですね
これならちゃんと333333333333333334になってくれます
Pythonならa // b + (a % b != 0)っていうやり方もありますけど
見た目的には(a + b - 1) // bのほうがかっこいいですかね

実際に書いたコード

N, K = map(int, input().split())

ans = N // (K + 1) + 1

print(ans)

C. No.478 一般門松列列

問題文はこちら
No.478 一般門松列列 - yukicoder

感想

なんかyukicoderでは定番問題みたいですね、門松列問題
門松列ってyukicoderオリジナルなんですかねえ

一般門松列列の定義の咀嚼に手間取りましたが、確かに門松列列の一般化になってますね
k = 0にするとちゃんと門松列列になります
で、与えられたn,kに対してどうやって作るかって話ですが
何か適当に1,0,2って書いてみて、こっから1,0,2,1,3,2,4,3,...
って増やしてけば無限に門松列が生成できるなあって気づきました
これは
偶数番目だけ抜き出すと1,2,3,4,...
奇数番目だけ抜き出すと0,1,2,3,...
ってなってるんですよね
つまり
a_2k = k + 1, a_(2k + 1) = k (k = 0,1,2,...)
って感じに作ってけばいいですね
で、必要なn - k - 2個分の門松列ができたら
残りは末尾の数で埋めてやればいいってのが考えでした
計算量はO(n)ですね

それを元に書いたコードがこちら

n, k = map(int, input().split())
num_k = n - k - 2

if num_k == 0:
    a = [0] * n
    print(*a)
else:
    a = [1, 0, 2]
    num_k -= 1
    i = 3

    while num_k > 0:
        if i % 2 == 0:
            a.append(i // 2 + 1)
        else:
            a.append((i - 1) // 2)

        i += 1
        num_k -= 1

    fil_n = a[-1]

    a += [fil_n] * (n - len(a))
    print(*a)

解説見るともっと簡単にやってました
1,3,2,4ってサイクルをつなげていくと無限に門松列ができるんですね
1,3,2,4,1,3,2,4,1,3,...
確かになります
なのでこれで必要な個数作って、後は先頭を1で埋めればいい
ってことになってて確かになーって思いました
例の最後がまさにこの方法で作ってたみたいです

D. No.479 頂点は要らない

問題文はこちら
No.479 頂点は要らない - yukicoder

感想

最終問題でした
★3だしグラフ問題だしどうせ解けないだろうなと思って
寝ようかなとか思ったんですがこの時点で1時間以上時間余ってた
のでせっかくなんでちょっとだけ考えてみようと思いました
結論からいうと、考え方はあってたけど実装方法が悪くてTLEして終了でした

以下自分のアルゴリズムの説明ですが解説と違うし
なんかややこしいしちょっと怪しげな感じもあるので
あんまり真面目に読まないでください
間違いがあったら指摘していただけると幸いです

頂点kを取ったときのコストは2^kになるという性質から
「頂点kを一つ取ったときのコスト > 頂点0,1,...,k-1を全て取ったときのコスト」
になってることが分かります、これが今回のキーポイントみたいです
もうちょっと言うと
「ある頂点kとそれより小さい頂点につながっている枝全てを回収するにはk自身を取るより、対になっているkより小さい頂点全てを取ったほうが安くなる」
っていう性質を使います

このことから、まず頂点n - 1は取らないほうがよいことが分かります
なので、頂点n - 1は「取らない」にします
そうすると、n - 1につながってる枝を回収するためにはその枝の対になっている頂点は必ず取らなければならないのでそれらの頂点を「取る」にします

次に「取る」「取らない」が定まってない頂点の中で最大の頂点を見つけてきます
キーポイントの性質から、この頂点より小さい頂点につながっている枝を回収するにはこの頂点自身を取るより、枝の対になっている小さい頂点すべてを取ったほうが安くなることが分かります
なのでこの頂点は「取らない」として、枝の対にある自身より小さい頂点は全て「取る」にします

問題は枝の対になってる頂点が自身より大きい場合ですが、これは既に「取る」になってるはずです
もし「取らない」になっているなら自身が既に「取る」になってるはずなので仮定に矛盾します

この操作を全ての頂点の「取る」「取らない」が確定するまで繰り返します
このアルゴリズムが終わった時、それは最適解になっているはずです

なんか分かりにくいので例を作りました
以下のようなグラフがあるとします

f:id:nanae1914:20170128142826j:plain

まずは一番大きい頂点5を「取らない」にします
そしてつながってる2,3を「取る」にします

f:id:nanae1914:20170128142831j:plain

次に「取る」「取らない」が確定してない頂点のうち
最大のものを見つけてきます、ここでは4です

この4を「取らない」にして、1,3を「取る」にします

f:id:nanae1914:20170128142835j:plain

最後に0を「取らない」にします
枝の対になっている頂点は全て0より大きいですが、それらは
すでに「取る」になっているので確かに0を取らなくても
0についてる枝を全て回収できているが分かります
これで全ての頂点について「取る」「取らない」が確定しました

f:id:nanae1914:20170128142841j:plain

以下実際にACもらったコードです
計算量はn回ループと「取らない」と判断した頂点の次数の総和なので
O(n + m)には収まってそうです
processed[i]は頂点iが「取る」「取らない」が確定したか否かを表してます

n, m = map(int, sys.stdin.readline().split())
edges = {i:set() for i in range(n)}
buy = ['0'] * n
processed = [False] * n

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    edges[a].add(b)
    edges[b].add(a)

for i in range(n - 1, -1, -1):
    if processed[i] == True:
        continue

    processed[i] = True

    for node in edges[i]:
        buy[node] = '1'
        processed[node] = True

ans = ''.join([str(b) for b in reversed(buy)])
ans = ans.lstrip('0')

print(ans)

yukicoderの★3解けたの初めてだったんで嬉しいです