Codeforces Round #401 (Div. 2) - D言語で競プロ

参加しました、３完でした
私にしては良く出来た回だったかなと思います

A.o
B.o
C.xxo

公式解説
Problem analysis of Codeforces Round #401 (Div. 2) - Codeforces

A. Shell Game

def solve():
    shells = [False] * 3
    n = int(input())
    x = int(input())

    shells[x] = True
    n %= 6

    for i in range(n, 0, -1):
        if i % 2:
            shells[0], shells[1] = shells[1], shells[0]
        else:
            shells[1], shells[2] = shells[2], shells[1]

    for i in range(3):
        if shells[i]:
            print(i)
            return None


if __name__ == '__main__':
    solve()

最初の問題ですね。これは実際に試してみると

0	1	2
1	0	2
1	2	0
2	1	0
2	0	1
0	2	1
0	1	2

となり、周期６で元の状態に戻ることが分かります。よって、nがいくら大きくても実際に操作するのはn % 6回だけでよいということになります。

B. Game of Credit Cards

最初に書いたコードがこれです。

def solve():
    n = int(input())
    Sn = list(map(int, input()))
    Mn = list(map(int, input()))

    cntM1 = Counter(Mn)
    cntM2 = copy.deepcopy(cntM1)

    # max-win
    maxwin = 0
    for d in Sn:
        for a in range(d+1, 10):
            if cntM1[a] > 0:
                cntM1[a] -= 1
                maxwin += 1
                break
        else:
            for a in range(0, d + 1):
                if cntM1[a] > 0:
                    cntM1[a] -= 1
                    break

    # min-lose
    minlose = 0
    for d in Sn:
        for a in range(d, 10):
            if cntM2[a] > 0:
                cntM2[a] -= 1
                break
        else:
            for a in range(0, d):
                if cntM2[a] > 0:
                    minlose += 1
                    cntM2[a] -= 1
                    break

    print(minlose)
    print(maxwin)


if __name__ == '__main__':
    solve()

勝ち数を最大にしたいときは、相手の手を前から順に見て行き、勝てる手があったらその中で一番小さい数字を出していく。勝てなかったらその中で一番小さい数字を捨てる。
負け数を最小にしたいときは、相手の手を前から順に見て行き、引き分けか勝てる手があったらその中で一番小さい数字を出していく。負け確定ならその中で一番小さい数字を捨てる。

という貪欲法です。これ何か嘘貪欲っぽいですが、なぜか通ってしまいました。
実際似たような問題がyukicoderの制限ジャンケンという問題です。相手の手が分かってる時にどう出すと点数が最大化できるか？という問題で「相手の手を順に見て行き、そこで点数が最大になるような手を出す」という貪欲法は誤回答になってしまいます。
これと似た状況なので、「相手の手を順に見ていって～」という解法は誤解法になる気がするんですが、なぜ通ったんでしょうかね？
今回のゲームはじゃんけんのように３すくみではなく、0 < 1 < 2 < 3 < ... < 8 < 9 と数字が大きいものほど価値が高いというシンプルな構造だったからなのかなと思います。
例えば上の状況＋「ただし、0は9に勝つことができる」だと、今回の私の解法では上手くいきませんね。

この問題はyukicoderの制限ジャンケンの正当解法のような解き方も可能で、実際こっちが正攻法かなと思います。
小さい方から「勝てる（または引き分け以上にできる）手を出来るだけその場所に割り当てていく」という方法ですね。
こういうのは順番を気にせずに「どうやって割り当てるとスコアが最大化できるか？」という問題だと捉えなおしたほうがシンプルですね。

def solve():
    n = int(input())
    sn = [0] * 10
    mn = sn[:]

    for i in input():
        sn[int(i)] += 1
    for i in input():
        mn[int(i)] += 1

    snc = sn[:]
    mnc = mn[:]
    for i in range(10):
        for j in range(i-1, -1, -1):
            if mnc[i] == 0:
                break
            tmp = min(mnc[i], snc[j])
            mnc[i] -= tmp
            snc[j] -= tmp

    max_win = n - sum(snc)

    snc = sn[:]
    mnc = mn[:]
    for i in range(10):
        for j in range(i, -1, -1):
            if mnc[i] == 0:
                break
            tmp = min(mnc[i], snc[j])
            mnc[i] -= tmp
            snc[j] -= tmp

    min_lose = sum(snc)

    print(min_lose)
    print(max_win)


if __name__ == '__main__':
    solve()

C. Alyona and Spreadsheet

「たくさんのクエリをどうやって効率よくさばくか」という問題ですね。codeforcesでは初めて当たりました。
クエリは「行列をl行からr行に制限したとき、１つでもソートされている列が存在するか？」という内容です。
これは
f[i] = (i行から始まり、j行までソートされている、というものの中で最も大きなj)
という配列を最初に作っておくと、クエリが与えられたときにf[l] <= rが成り立つかを調べればよいので各クエリに対してO(1)、全てのクエリに対してO(k)で答えられます。
そしてこのf[i]はAを列ごとに見て行って、尺取り法（？）の要領で更新していけばいいのでO(nm)で可能で、全体の計算量はO(nm + k)となります。

import sys

def solve():
    n, m = map(int, sys.stdin.readline().split())
    A = [[int(i) for i in sys.stdin.readline().split()] for j in range(n)]
    q = int(sys.stdin.readline().rstrip())
    querys = [tuple(map(int, sys.stdin.readline().split())) for i in range(q)]

    f = [i for i in range(n)]

    for j in range(m):
        s = 0
        for i in range(n):
            if i == n - 1 or A[i][j] > A[i + 1][j]:
                for k in range(s, i + 1):
                    f[k] = max(f[k], i)
                s = i + 1

    ans = []

    for l, r in querys:
        if r-1 <= f[l-1]:
            ans.append('Yes')
        else:
            ans.append('No')

    print(*ans, sep='\n')

if __name__ == '__main__':
    solve()

割とスッキリ解けたので結構嬉しかったです。ただ、入力が多いのにsys.stdin.readline()を使ってなくて最初２回ほどTLEして焦りました。

queryの複数形はqueriesなのにquerysになってますね。