yukicoder contest 157 - D言語で競プロ

参加しました、結果は３完
あまり芳しくなかったですね

A.o
B.o
C.o
D.-
E.x

A. No.485 方程式のお勉強

B / Aが余りのある割り算ならNO、そうでなければ答えを出力します
0割りのコーナーケースがあるかなと思ったらそれは制約によって除外されていました

def solve():
    A, B = map(int, input().split())

    if B % A != 0:
        ans = 'NO'
    else:
        ans = B // A

    print(ans)

if __name__ == '__main__':
    solve()

B. No.486 3 Straight Win(3連勝)

No.486 3 Straight Win(3連勝) - yukicoder

最初碌に問題文を読まずに「勝った数が多い方が勝ち」と思い込み、次は「先に３勝した方が勝ち」と誤読しました
なかなか酷かったです
解き方は前から読んでいき、両方の勝ち数をカウント（負けた瞬間リセット）するとどちらかが３になったら３連勝したほうを出力します
最後まで読んでなおかつ決まらなかったら引き分けです

def solve():
    S = input()
    N = len(S)

    cnt_o = 0
    cnt_x = 0

    for c in S:
        if c == 'O':
            cnt_x = 0
            cnt_o += 1
            if cnt_o >= 3:
                print('East')
                return None
        else:
            cnt_o = 0
            cnt_x += 1
            if cnt_x >= 3:
                print('West')
                return None

    print('NA')

if __name__ == '__main__':
    solve()

C. No.487 2017 Calculation(2017の計算)

No.487 2017 Calculation(2017の計算) - yukicoder

pythonはpow(x, y, z)とすると(x ^ y) % zを高速に計算してくれるそうです（べき剰余というらしい）
なのでそれを使いました、ちょっとズルっぽい感じですが……
想定解はmod取りながらforループ回すとかそんな感じなんですかね、2017回ぐらいなら普通に間に合いますね
ちょっと調べたらダブリングを使えばO(log(y))ぐらいで出来るみたいですね

def solve():
    M = int(input())
    ans = 0

    ans += 2017 % M
    ans += pow(2017**2, 2017, M)
    ans %= M

    print(ans)

if __name__ == '__main__':
    solve()

D. No.488 四角関係

No.488 四角関係 - yukicoder

N <= 50 と小さいので50C4 通りを全て試せばいいかと思いましたが、４点取ってきたときにそれが四角関係になっているかを判定するのがめんどくさそうというか分からなかったので飛ばしてしまいました
各ノードの次数が２になってるだけでは、何かクロスしてつながるのが省けないからダメですよねえ
……あれ？　別に図的にクロスしててもズラしたりすればそれも四角関係ですね。例２の（１，２，５，６）も図的にはクロスしてるけど四角関係ですね。
ってことは単に４点に制限したときのグラフの各ノードの次数が２であることだけを調べればいいだけでしたか
今提出したらACなりました、あらら。考察不足でしたね。そもそも
”ここで言う四角の関係とは、4つのノードだけで考えた時、それが4点の閉路グラフであることを言います。”
ってちゃんと書いてるから図的に四角じゃないからダメとかそういうのは関係無かったですね。

（追記）
「グラフを４点に限ったときに各ノードの次数が２であるものだけをカウントすればよい」
については「自己辺（自己ループ）、二重辺が無く、かつ頂点数が５以下である」から必要十分になってるっぽいですね
頂点数６の閉路グラフを数えるとかだと、各ノードの次数が２であることだけを調べるでは不十分ですね
（３角形が２つある奴とかも閉路グラフとして数えてしまう

というわけで今書いたコードです
グラフの問題って幅優先探索とかすることが多いので普段は隣接リスト表現で持つことが多いですが
この問題だと隣接行列表現で持っておいた方が楽ですね、４点以外を無視してグラフを作るってことをやるので
itertoolsのcombinationsが凄く便利です、けどいつもcollectionsにあると勘違いしています

from itertools import combinations

def solve():
    N, M = map(int, input().split())
    Adj = [[0]*N for i in range(N)]
    cnt = 0

    for lp in range(M):
        a, b = map(int, input().split())
        Adj[a][b] = 1
        Adj[b][a] = 1

    for comb in combinations(range(N), 4):
        for u in comb:
            deg = 0
            for v in comb:
                deg += Adj[u][v]
            if deg != 2:
                break
        else:
            cnt += 1

    print(cnt)

if __name__ == '__main__':
    solve()

E. No.489 株に挑戦

No.489 株に挑戦 - yukicoder

AOJに似たような問題があるんですよね

最大の利益 | アルゴリズムとデータ構造 | Aizu Online Judge

最初のほうにある割にはかなり難しかったです、結構時間使って考えたのを思い出しました
これを解いたことがあって似てるなあって思ったから解けるかな？と思ったんですが何か変なコード（明らかに間違ってるコード）を書いてしまいダメでした
もうちょっと時間かけて考察すれば解ける気がするので一旦保留にしています