読者です 読者をやめる 読者になる 読者になる

Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)

参加しました、4完でした
codeforcesで4完できたのは初めてでした
いつもより長く3時間あったから、というのもありますがちょっと嬉しかったです

A.o
B.o
C.x(hacked)o
D.o
E.xx

http://codeforces.com/contest/765

公式解説
Codeforces Round #397 Editorial - Codeforces

A. Neverending competitions

Problem - A - Codeforces

問題概要

Jinotega君がコンテストのために、海外を飛び回ることになった。
フライトは全部でn回あって、地元からコンテスト地へ飛んでコンテストが終わったらコンテスト地から地元へ飛んで帰ってくる。
Jinotega君の地元がAAA、フライトのデータが"XXX->YYY"というn行のデータで与えられるので今Jinotega君が地元にいるか、コンテスト地にいるかを判定せよ。
Jinotega君は最初は地元から出発している。

制約

  • 1 <= n <= 100

感想

いきなり問題文が長く、かつ入力形式などがややこしいが

  • Jinotega君は最初地元にいる
  • Jinotega君は必ず、地元→コンテスト地→地元と往復する(コンテスト地から別のコンテスト地へ行くことは無い)

ということが分かっているので、全てのデータを読み込むまでもなくnの偶奇だけ見ればよい。

このことさえ分かれば悩むことは特に無いが、英語力が低いので時間がかかってしまった。

def solve():
    n = int(input())

    if n % 2 == 0:
        ans = 'home'
    else:
        ans = 'contest'

    print(ans)


if __name__ == '__main__':
    solve()

B. Code obfuscation

Problem - B - Codeforces

問題概要

Kostya君はコードフォースのコンテストが大好きだ。けど、彼はよくハックされてむかつくので彼はソースコードを難読化することに決めた。
彼は変数名を変換することにした。最初にでてくる変数名は全てaに置き換え、次にでてくる変数名をbに置き換え、……という感じだ。
彼のソースコードは難読化する前は全て変数名の長さは2文字以上で、かつ変数の種類は26種類以内であるとする。

彼のソースコードにでてくる変数を順に並べた文字列が与えられるので、それが難読化された状態のものかを判定せよ。

制約

  • 1 <= len(S) <= 500

感想

素直に文字列を前から1文字ずつ読んでいき、次に現れる新しいアルファベットか今まで出てきたアルファベットなら次へ進む(新しいアルファベットなら次に現れるアルファベットを更新しておく)、
そうでなければルールに沿って難読化できてないのでそこで打ち切り、全部読めたらOK

という感じでやった。計算量はO(len(S))

def solve():
    S = input()
    ch = ord('a')

    for c in S:
        if ord(c) > ch:
            print('NO')
            return
        elif ord(c) == ch:
            ch += 1
        else:
            pass
    
    print('YES')


if __name__ == '__main__':
    solve()

どうでもいいですけど、codeforcesでハックされないようソースコードを意図的に難読化するのって規約違反だったと思います
ちなみに今回初めてハックされたんですが普通にありがたいし相手にとっても嬉しいだろうからwin-winのシステムでなかなかいい仕組みだなあって思いました

C. Table Tennis Game 2

Problem - C - Codeforces

問題概要

MisyaとVanyaがテニスの試合を何セットかした。そのテニスではどちらかがkポイント先取したら、そのプレイヤーを勝ちとして1セットを終え、両者のポイントをリセットする。
全てのセットを終えた後の両者のポイントはMisyaがa、Vanyaがbであった。
これらのk, a, bが与えられるのでこの情報から彼らが最大何セットの試合をしたか、あるいはその状況が不可能であることを判定せよ。

制約

  • 1 <= k <= 10^9
  • 1 <= a, b <= 10^9
  • a + b > 0

感想

考えやすくするために、a >= bを仮定しておきましょう。
最大の試合数にするには、明らかにk - 0または0 - kとなったセットが多くなるほうがいいことが分かります。
例えば、k, a, b = 11, 11, 22だったとすると5 - 11, 6 - 11の2セットと考えるより、11 - 0, 0 - 11, 0 - 11と3セット行われたと考えた方が多くなります。
このことから、a / k, b / kとすればaが勝った回数、bが勝った回数が求まります。それらの和が最大セット数となるはずです。

ただし気をつけるべきことがあって、a % k, b % kを消費できるような試合ができるかどうかを考慮する必要があります。
例えば、'11 14 8'というケースを考えると、セット数は1ですが、このとき、11 - 8という試合をすればb % kを消費することはできましたが、14 % 11 = 3を消費する試合ができません。
なのでこの場合は不可能ということになります。
一方、'11 14 13'ならセット数は2で、実際に11 - 2, 3 - 11という試合をすることができますから答えは2になります。

これを踏まえて最初、こんなコードを書いてました

def solve():
    k, a, b = map(int, input().split())
    a, b = max(a, b), min(a, b)
    win_a, rem_a = divmod(a, k)
    win_b, rem_b = divmod(b, k)
    sets = win_a + win_b

    if sets >= 2:
        ans = sets
    elif rem_a > 0 and rem_b > 0:
        ans = -1
    else:
        ans = sets if sets > 0 else -1

    print(ans)

if __name__ == '__main__':
    solve()

セット数が2以上なら、上で言ったようなa % k, b % kをともに消費できるような試合ができるからそのまま出力。
セット数が1以下なら、どちらかしか消費できないから、a % k > 0 で b % k > 0のとき、不可能。
それ以外なら、セット数0でなければそのままセット数を出力。

……分かりにくいですがこんなコードを書いていました。これは即座にハックされました。
例えば、'11 23 0'というケースを投げると、私のソースコードでは'2'を返します。しかし実際これは明らかに'-1'を返すべきです。
11 - 0, 11 - 0という試合しかできず、23 % 11 = 1が消費できません。bが勝ってくれる試合が無いからですね。
あと、'11 14 0'とかもダメですねこれ。場合分けが全く機能してないですね……。

aの勝ち回数、bの勝ち回数をひっくるめたセット数で場合分けしてるからダメだったんですね。
というわけで正しく直したコードが以下

def solve():
    k, a, b = map(int, input().split())
    a, b = max(a, b), min(a, b)
    win_a, rem_a = divmod(a, k)
    win_b, rem_b = divmod(b, k)
    sets = win_a + win_b

    if sets == 0:
        ans = -1
    else:
        if win_b == 0 and rem_a > 0:
            ans = -1
        else:
            ans = sets
            
    print(ans)


if __name__ == '__main__':
    solve()

セット数0っていうのは無いので不可能
セット数1以上のときは、bの勝ち回数が0で、a % k > 0ならa % kを消費できる試合ができないので不可能
(b % k についてはセット数1以上のときaは少なくとも1回以上は勝つので必ず消費できる)
そうでないときはa % kを消費できる試合ができるのでセット数を出力

……としました。a >= bとなるよう置き直したので分岐がシンプルになっているような気がします。
これで通りました。

ハックしてくれて助かりました。

D. Artsem and Saunders

問題概要

[n] := {1, 2, ..., n}と定義する。

与えられた写像f:[n] -> [n]に対して以下の条件を満たす正の整数m, 写像g:[n] -> [m], h:[m] -> [n]を探せ。

  • g(h(x)) = x (for all x in [m])
  • h(g(x)) = f(x) (for all x in [n])

ただし、そのようなm, g, hが存在しない場合は-1を出力せよ。

感想

難しそうな問題です。

まずは考えやすそうなケースから考えます。fが全単射、すなわちfが置換であるときに限定して考えてみます。
するとf = id(恒等写像)なら例3にもあるように、m = n, g = id, h = idとすれば明らかに題意を満たします。
では恒等写像でない置換の場合は? これは何か無理そうです。実際例3はf = (2 1)という置換ですがこれは無理なようです。

fが全単射でない場合で、もうちょっと具体的な例を考えてみます。
例えば、f = (2 2 2 3 5)という写像があったとします。
これは図にすると以下のような写像です。

f:id:nanae1914:20170216114026j:plain:w400

まず、h(g(x)) = f(x)となるような写像が作れないか?を考えてみます。
これはそんなに難しくなさそうです。fで行き先が同じになるような要素をグルーピングして、それらに番号付をするという写像をgにします。
この場合は g = (1 1 1 2 3)という感じです。
そして、hはその集合に対するfの値を対応させる写像にします。
この場合はh = (2 3 5)です。
これを合成すると確かにh(g(x)) = fになります。おお、できました。
これでg(h(x)) = xも成り立っていれば題意を満たすg, hになっています……が、この場合はgh = (1 1 3)となってしまいます。ダメでした。
なぜだめなんでしょうか。g(h(1)) = g(2) = 1, g(h(3)) = g(5) = 3なのでこの2つはいいみたいですが、g(h(2)) = g(3) = 1なのでここがダメですね。
hで移すときに、違うグループに行ってしまうのでgで戻ってこれないようです。

上のfをちょっと書き換えてf = (3 2 3 3 5)としてみます。

f:id:nanae1914:20170216114338j:plain:w400

すると、さっきと同じようにg, hを作ると、g = (1 2 1 1 3), h = (3 2 5)となり、hg = f, gh = idが成り立っていることが確認できます。
どうやら、任意のa in f([n])について、a in f^(-1)(a) が成り立っていたらこの方針で出来そうで、成り立たないものがあれば無理そうだと思いました。
確かに成り立っている場合は作ったg, hが題意を満たすことは分かります。しかし成り立っていないときも本当にダメなんだろうか、と考えるとすぐには分かりませんでした。

しかし悩んでいても分からないのでこの辺で考察を打ちきって、実際にコードを書いて出してみることにしました。

from collections import defaultdict

def solve():
    n = int(input())
    f = [int(i) for i in input().split()]
    inv = defaultdict(set)

    for i, y in enumerate(f, start=1):
        inv[y].add(i)

    m = len(inv)
    g = [0] * (n + 1)
    h = [0] * (m + 1)

    for i, x in enumerate(inv, start=1):
        if x not in inv[x]:
            print(-1)
            return

        for a in inv[x]:
            g[a] = i

        h[i] = x

    print(m)
    print(*g[1:])
    print(*h[1:])

if __name__ == '__main__':
    solve()

invがfの逆写像ですね。defaultdictは初めて使いました。対応するキーが無いときは自動で空集合を作ってくれます。

これで出したらpretestが通ったので多分大丈夫そうだなと思って次にいくことにしました。
結局これは通ってたんですが証明できてないものをpretestで通して安心するのはマズいなあと思いました。実際Cはpretestに通ってハックされたわけですし……

というわけで証明を考えているのですが上手く示せません。Editorialも今回なぜか出てないし。どうしよう。
とりあえず現状分かっていることを書きだしてみます。

故に、f(x) \neq f(y)となり、対偶を取ると、f(x) = f(y)ならばg(x) = g(y)
このことから写像fで行き先が同じになるものでグルーピングした結果と、写像gで行き先が同じになるものでグルーピングした結果は一緒になる。
よってgの全射性より、m = (f([n])の要素数)でなければならないことが分かる。

……とか書いてたら公式のEditorialが出ていました。もっと簡単に示せるみたいです。
f(f(x)) = f(x)(for all x in [n])であることを示すことと、任意のa in f([n])についてa in f^(-1)(a)を示すことは同値なので前者のほうを示す。
h(g(x)) = f(x), g(h(x)) = xより、f(f(x)) = h(g(h(g(x)))) = h(1(g(x))) = h(g(x)) = f(x)
よって題意を満たすm, g, hが存在するための必要条件はf(f(x)) = f(x)が成り立っていることである。

という感じでした。なるほどなぁ。
f(f(x)) = f(x)という性質をベキ等性(idempotent)というらしいです。

E. Tree Folding

Problem - E - Codeforces

問題概要

木をパタパタと折りたたんで行って一本のパスにできるか?
できるならそのパスの最短長さを出力せよ

感想

一応やってたけど、そもそも問題をちゃんと理解できていなかったので全然ダメでした。