ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

codeforces

２完でした、C,Dは取り組んではみたものの解けませんでした

A.o
B.o
C.-
D.-

http://codeforces.com/contest/776
公式解説
ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) Editorial - Codeforces


A. A Serial Killer

Problem - A - Codeforces

def solve():
    p1, p2 = input().split()
    n = int(input())
    print(p1, p2)

    for i in range(n):
        s1, s2 = input().split()
        if s1 == p1:
            p1 = s2
        else:
            p2 = s2
        print(p1, p2)

if __name__ == '__main__':
    solve()

特に工夫無く殺された人を新しい人で書き換えて出力しただけですね。
A問題は簡単な代わりに問題文が長いという感じですがこれくらいなら読めるようになってきました。

B. Sherlock and his girlfriend

Problem - B - Codeforces

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

    if n <= 2:
        k = 1
        ans = [1]*n
        print(k)
        print(*ans)
    else:
        k = 2
        ans = color(n)
        print(k)
        print(*ans)

def color(n):
    res = [1] * (n + 2) # 0, 1, 2, 3, ..., n + 1
    for p in range(2, n + 2):
        if res[p] != 1:
            continue
        for q in range(p*p, n + 2, p):
            res[q] = 2

    return res[2:]

if __name__ == '__main__':
    solve()

問題文を読むと「片方の値段がもう片方の素因数となっていたら異なる色にしなければならない」と書いてました
ということは少なくとも素数の宝石同士は全て同じ色にしてよいです
さらに合成数はそもそも素数じゃないので合成数の宝石同士も全て同じ色にしていいです
でも合成数と素数まで同じ色にしてしまうと、条件を満たさなくなってしまうのでこの２つは違う色にしておく必要があります
というわけで素数→１、合成数→２とさえしておけばこれで条件を満たす色分けになってます
これはエラトステネスの篩を用いることで計算量O(NloglogN)で実現できます
ただし、n <= 2のときは素数しかないのでそこだけ場合分けしてます

このエラトステネスの篩を応用する問題は前にcodeforcesで経験したことがあります
Problem - B - Codeforces
この問題は最初に十分大きいMAXまでの全ての整数についてエラトステネスの篩で異なる素因数を列挙しておいて
後で各s_iにある素因数p_iが含まれていたらカウントして、一番多くカウントされたものを取ってくればいいという方法があります
この問題だとMAX <= 10^5なので各s_iに含まれる異なる素因数の数は高々６個くらいです（素数階乗より）
なのでこの方法でやると計算量は高々O(MAXloglogMAX + N)ぐらいになって、s_iを一個ずつ素因数分解してカウントという方法O(N * sqrt(MAX))よりかは速くなります
まあこの問題はN <= 10^5なのでC++なら後者の方法でも楽々通るんですがpythonだと後者の方法では通らなくて、前者の方法でやるとpythonでも通る、ということで印象的でした

エラトステネスの篩を応用する問題は割とでてくる印象があるのでしっかり解けるようにしたいですね

C. Molly's Chemicals

Problem - C - Codeforces

難しかったです、というか手も足も出ませんでした
累積和を使えば各区間和はO(1)で出来るとか基本的な考え方はだいぶ馴染んできたんですがそっから進まなかったですね
DPとか使うのかなーとか考えてたんですがどうやって漸化式立てるの？みたいな感じで停滞してました

解説見ると累積和を使って区間和を書くってのは使うみたいで、そこから式変形してp[r] = k^i + p[l - 1]にして、k^iのほうをループ回してカウントするってやってて
ははぁ～って感じでした。いや全く思いつきませんでしたね……
この方法だと確かに一回のループは50回くらいでそれをn <= 10^5回回すのでまあ十分間に合うって感じでしょうか
ただ辞書を使うのもあってpythonでは重く、pypyで通しましたが
「区間和がk^iになっているのってどうやって調べるんだ？」ってずっと考えてたので、何か発想の転換が必要な問題だなあという気がします
けど結構な人数解けてるので自然な考え方なのかなあ……あるいはこういう問題って結構出るんでしょうか？

というわけで一応コード、解説のコードを参考にしながら書きました

import sys
from itertools import accumulate
from collections import Counter

def solve():
    n, k = map(int, input().split())
    A = [int(i) for i in input().split()]
    cs = [0] + list(accumulate(A))
    S = Counter()
    ans = 0

    if k == 1:
        for i in range(n, -1, -1):
            if i == n:
                S[cs[i]] += 1
                continue

            if cs[i] + 1 in S:
                ans += S[cs[i] + 1]

            S[cs[i]] += 1
    elif k == -1:
        for i in range(n, -1, -1):
            if i == n:
                S[cs[i]] += 1
                continue

            if cs[i] + 1 in S:
                ans += S[cs[i] + 1]
            if cs[i] - 1 in S:
                ans += S[cs[i] - 1]

            S[cs[i]] += 1
    else:
        for i in range(n, -1, -1):
            if i == n:
                S[cs[i]] += 1
                continue

            w = 1
            while abs(w) < 10**14 + 1:
                if cs[i] + w in S:
                    ans += S[cs[i] + w]
                w *= k

            S[cs[i]] += 1
    print(ans)


if __name__ == '__main__':
    solve()

D. The Door Problem

Problem - D - Codeforces

こっちも難しかったです。こっちのほうがCより解きやすそうな気がしたのでこっちもそれなりに考えてたんですがやはり解けず。
問題文にある「どのドアも２つのスイッチで制御されている」っていう条件がキーっぽいなあとかは思ってました。
スイッチをn次元ベクトルと見なして最初のドアの状態に直交するベクトル（０，１が反転したベクトル）が作れればいいってことなんだけど
そんなんどうやってやるんだ、行列を上手く操作してやるのか？ビット演算を使うのか？とかそんなことを考えていました

解説読んだら目から鱗な解き方でした
まずドアを辺、スイッチを頂点としたグラフを構成して、「最初からドアが開いてたら両端の頂点は同じ色にする、ドアが閉じていたら両端は異なる色にする」というルールで頂点を色づけしていって
矛盾無く全ての頂点に色がつけられたらYES、そうでないならNOとするというやり方でした
ポイントは「最初からドアが開いてたらそれを制御する２つのスイッチの状態は同じでなければいけない、逆に閉じていたら２つのスイッチの状態は異なっていないといけない」というところですね
だから上のやり方で上手くいくということですね

ドアを辺、スイッチを頂点としたグラフにするってのがまず思いつきません
けどキーポイントとなるところには気づきたかったなあと思いました
この手の問題では「最終状態が達成できたとしたら、それはどういう状況でなければならないか？」というのを考えるのはしばしば重要だなあと思いました

コーディングはまだやってません、暇ができたらやろうと思います