yukicoder contest 156

参加しました、3完でした

A.o
B.xo
C.o

A. No.480 合計

問題概要

1~Nまでの合計を求めよ

制約

  • 1 <= N <= 100

感想

1~Nまでの整数の和の公式 N*(N+1)//2 を使って答えを求めました。
Nの上限が小さいのでfor文を回して求めると言う方法もありますね。
★1らしい★1の問題だと感じました。

実際に書いたコード、O(1)

def solve():
    N = int(input())
    ans = N * (N + 1) // 2

    print(ans)

if __name__ == '__main__':
    solve()

なぜ解けたのか?

  • 有名な問題であり、何度も解いたことがあったから

B. No.481 1から10

No.481 1から10 - yukicoder

問題概要

1から10までの整数を書いたつもりが、実際はそこには9個しか書かれていなかった。
その9個の整数が与えられるので、書かれなかった整数を求めよ。

感想

書いた整数たちを集合として受け取り、{1,2,...,10}の集合からその集合を引くと書かれなかった数字が1つだけ属する集合になります。
なのでその集合から1つ数字を取り出せばそれが答えになっています。

というめちゃくちゃ素朴な考え方で解きました。

def solve():
    Bs = set([int(i) for i in input().split()])
    ans = set(range(1, 11)) - Bs

    print(ans.pop())

if __name__ == '__main__':
    solve()

あんまり使うことが無いですが、setからある要素をpopで取り出すことができます。
もちろん一般には何が出てくるかは分かりませんが、この場合は一意に定まるので大丈夫です。
1回間違えたのは、range(1,11)とすべきところをrange(1,10)とやっていたという典型的な凡ミスですね……。

それでもっと賢い方法があって、55 - sum(Bs)とやる方法があったようです。
スマートでいいですね、思いつきもしなかったです。

def solve():
    Bs = [int(i) for i in input().split()]
    ans = 55 - sum(Bs)

    print(ans)

なぜ解けたか?

  • 自然に考えれば自然に解法が浮かぶ問題だった
  • 制約が小さかったので素朴にやっても大丈夫だった

C. No.482 あなたの名は

No.482 あなたの名は - yukicoder

問題概要

1~Nを適当に並び替えた数列D = {D_1, D_2, ..., D_N}が与えられる。
この中から2つの数字を選んで、その場所を入れ替えるという操作ができる。
この操作を"ちょうど"K回やったとき、1,2,3,...,Nと昇順に並べることができるかを調べよ。

制約

  • 2 <= N <= 200,000
  • 1 <= K <= 10^12
  • 1 <= D_i <= N

感想

サンプルを見たりちょっと考えたりすると、最短の操作回数で並び替えられたら後は適当に1,2を入れ替えるを繰り返せば余った分を消費できるから最短の操作回数がK以下で、かつ最短の操作回数とKの偶奇が一致してたらYESとなりそうだということが分かります。
じゃあ偶奇が一致しなかったら? となりますがこの場合はダメです。
「何か上手いことスワップの順番を変えたら偶奇が違っててもちゃんと並び替えられるんじゃ?」とか思いますが、一般的に無理だということが数学的に示されていてこれを置換の偶奇性と言うらしいです。
大学で線型代数をやったら行列式を定義するときにこんなことを習います。証明はあまり自明じゃなかったと思います。

ともあれ、この問題を解くにはDを昇順に並び替えるための最小の操作回数が求められればよいということが分かります。
これはどのようにして求めるかというと、Dを置換として見て、それを巡回置換の積に分解します。
すると長さkの巡回置換は最小でk - 1個の互換の積で表せることが知られています。
(もしk - 1個未満の互換の積で表せたとすると、元の並びに直すときに一度に2つの数字が元の場所に戻るようなスワップが2回以上あることになります。
これの意味するところは、巡回置換が2つ以上あるということなので矛盾です。)

なので各巡回置換の長さ - 1の総和がDを昇順に並び替えるための最小の操作回数となります。

というわけで実際のコードがこちら
計算量はDの各巡回置換の長さを調べるためにかかるO(N)となります

def solve():
    N, K = map(int, input().split())
    Ds = [int(i) - 1 for i in input().split()]
    checked = [False] * N
    num_gokan = 0

    for i in range(N):
        if checked[i]:
            continue
            
        checked[i] = True

        len_cyc = 0
        nxt = Ds[i]

        while not checked[nxt]:
            checked[nxt] = True
            nxt = Ds[nxt]
            len_cyc += 1

        num_gokan += len_cyc

    if num_gokan <= K and num_gokan % 2 == K % 2:
        ans = 'YES'
    else:
        ans = 'NO'

    print(ans)

if __name__ == '__main__':
    solve()

これの類似問題として、置換に含まれる巡回置換の個数を数えるという問題がcodeforcesに出ていました。
Problem - A - Codeforces
私のブログでも感想を書いたこれですね
Codeforces Round #393 (Div. 2) - Pythonで競プロ

これで置換を巡回置換に分解するコードを書いていたので、今回すんなりとこの解法をコードにすることができました。
こういう形で経験が生きると嬉しいですね。

なぜ解けたか?

  • 置換の性質について、ある程度知識があった
  • 過去に同じような問題を解いた経験があった

D. No.483 マッチ並べ

No.483 マッチ並べ - yukicoder

問題概要

平面上にマッチをN本並べる。
マッチをどの場所に置くかという情報が与えられるので、マッチの頭薬が重ならないように並べられるかどうかを調べよ。

制約

  • 1 <= N <= 100
  • マッチの両端は整数座標上に位置する
  • マッチは横に置くか縦に置く

感想

総当たりは2^Nなので無理ですね。なので何か上手い方法を考える必要があります。

とりあえず絵を描いて考えると、まずサイクルがあったら無理なのか? と考えます。
確かにサイクルが無い場合は木になりますから、ルートからバーッと流せば頭薬が重ならないようにできることはすぐに分かります。
けれど、サイクルがあったらダメかというとそういうわけではなく、例えば以下のように置けば頭薬が重ならないように置くことができます。

f:id:nanae1914:20170213104040j:plain:w400

だから、サイクルは1つあってもいいようです。でも例にあるように8みたいなのはダメですね。
ということはサイクルが2つ以上繋がってたらダメかな? って考えます。
確かに絵を描いてるとサイクルが2つ繋がってたら無理だなーって思います。1点でつながってる場合も含めて。
それで良く考えると別に直につながってなくても、同じ連結成分にサイクルが2つある時点でダメだなあと分かります。
なぜなら、サイクルに属する頂点は全て既に頭薬がありますから、そこにつながっているサイクルから外れる辺にマッチを置こうとするとマッチの頭薬じゃない方を置かなきゃいけません。
するとそれが流れていくと頭薬のあるほうがもう一つのサイクルにいずれぶつかるわけですが、そのサイクルの全ての頂点も既に頭薬がありますから必ず頭薬がぶつかることになり、無理だと分かります。
f:id:nanae1914:20170213104100j:plain:w400

まとめると、各連結成分においてサイクルが2つ未満ならOK,2つ以上サイクルがあるならダメです。
考え方は分かりました。問題は実装です。どうやってサイクルの数を検出するのでしょうか?
ここで詰まりました。そもそも閉路を検出するコードを書いたことが無いし、ましてや何個あるか、というコードをぱっとかけそうにありません。
いろいろググってみたりしましたが、何かよく分からなかったので解く事を諦めました。

解説を見るとオイラーの定理を使うと簡単にサイクルの数が調べられたみたいです。(連結グラフの場合)
オイラーの定理は、ある連結なグラフにおいて頂点の数をv, 辺の数をe, 面の数をfとすると
v - e + f = 2
が成り立つというものです。ただし面の数には外側の領域を含むみたいです。
平面グラフとオイラーの定理の応用 | 高校数学の美しい物語

これを使うと頂点の数と辺の数さえ分かれば、面の数、つまりサイクルの数が分かります。
外側の領域も面として1つと数えるので閉路が2個以上あるとはf >= 3であることを意味します。
これはオイラーの定理より、v - e <= -1, つまり v + 1 <= e であることと同値なので、ある連結成分についてこの不等式が成り立っているものがあればNO、
全ての連結成分で成り立っていなければYESとなります。

ここまで理屈が分かっても実際に実装するのはちょっと面倒だなと感じました。慣れてないせいかもしれないですが……
幅優先探索を使って、頂点と辺を色分け(連結成分に分解)して、後はそれぞれの連結成分の頂点の数と辺の数を算出して比較ということをやってます。
インプットで座標をノードに変換したりするのが地味に面倒です。
全体的にもっといいやり方がありそうな感じはします。

from collections import deque

def paint_col(Adj, cols_v, cols_e, i, col):
    cols_v[i] = col
    nxts = deque([i])

    while nxts:
        u = nxts.popleft()

        for v in Adj[u]:
            if cols_e[min(u, v), max(u, v)] == 0:
                cols_e[min(u, v), max(u, v)] = col
            if cols_v[v] == 0:
                cols_v[v] = col
                nxts.append(v)

    return None

def solve():
    N = int(input())
    p2n = {}
    node = 0
    Adj = []
    cols_v = []
    cols_e = {}

    for i in range(N):
        r0, c0, r1, c1 = map(int, input().split())

        if (r0, c0) not in p2n:
            p2n[r0, c0] = node
            cols_v.append(0)
            node += 1
            Adj.append([])
        if (r1, c1) not in p2n:
            p2n[r1, c1] = node
            cols_v.append(0)
            node += 1
            Adj.append([])

        u, v = p2n[r0, c0], p2n[r1, c1]
        Adj[u].append(v)
        Adj[v].append(u)
        cols_e[min(u, v), max(u, v)] = 0

    col = 1

    for i in range(len(cols_v)):
        if cols_v[i] == 0:
            paint_col(Adj, cols_v, cols_e, i, col)
            col += 1

    for c in range(1, col):
        num_v = sum(i == c for i in cols_v)
        num_e = sum(i == c for i in cols_e.values())

        if num_v + 1 <= num_e:
            print('NO')
            break
    else:
        print('YES')

if __name__ == '__main__':
    solve()

他の人のコードを見ていたら「次数が1の頂点につながっているマッチを取り除く」という操作を次数1の頂点が無くなるまでやると、
閉路が0個の連結成分→無くなる
閉路が1個の連結成分→その閉路だけになる
閉路が2個以上の連結成分→閉路と、その閉路をつなぐ辺だけが残る
という性質を利用して、最終形の全ての頂点の次数を調べて、全ての頂点の次数が2以下なら上の2つの場合、1つでも次数3以上の頂点があれば下の場合になるというやり方で判別してました。
このやり方も分かりやすくていいなあ、と思いました。

なぜ解けなかったか?

  • 閉路の数を検出する方法を知らなかった(実装レベルでのつまづき)