京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200)

A~Cに回答できました.

すごい解説:

A - Century

西暦1〜100年が1世紀,101〜200年が2世紀,...です.100で割って,天井関数・床関数などでうまい具合に出力すればよいです.
参考:床関数・天井関数と関係式 - Notes_JP

import math
print(math.ceil(int(input())/100))

別な書き方:
Submission #22392191 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)
Submission #22392267 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

B - 200th ABC-200

こうしました.

n, k = map(int, input().split())

for _ in range(k):
  if n % 200 == 0:
    n //= 200
  else:
    n = 1000*n + 200
    
print(n)

if文はN%200でFalseで判定したほうがPython的には素直かもしれません:
Submission #22394380 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

文字列→intとしているものもありました:
Submission #22392499 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

C - Ringo's Favorite Numbers 2

「200で割った剰余が同じものを2つ選ぶ方法」を数えればよいです.

n = int(input())
a = list(map(int, input().split()))
a = [a[i]%200 for i in range(n)]

ans = 0
for i in set(a):
  tmp = a.count(i)
  ans += tmp*(tmp-1)//2
  
print(ans)

剰余分のリストを用意する回答も多かったです:
Submission #22398336 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

似た回答ですが,組み合わせの数え方がキレイ.自分自身と過去に出てきた同じ剰余との組み合わせ(=過去に出てきたものの個数)を都度足していけばよい(式で$\sum_{k=1}^{n} k = n(n+1)/2$だから,$n(n-1)/2=\sum_{k=1}^{n-1} k$,と解釈することもできる).
Submission #22396736 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

D - Happy Birthday! 2

なるほど...
Submission #22391351 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

  • 201回までに止まることを前提に,$2^{N}$通りの部分列を順に見ていく
    • マスクビットmaskで,部分列の和がtotal = sum(A[i] if mask >> i & 1 == 0 else 0 for i in range(N))と簡単にかける.
    • memo[total%200]で,totalを生成した部分列(mask)を記憶.これにより,①すでに同じ剰余のものが出たかの判定,②その部分列の復元,ができる.
  • Noは,201通りの部分列がつくれない数列で起こり得る.

E - Patisserie ABC 2

Dを飛ばしてこっちをやっていました.

【後で読む】
Submission #22387166 - KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)

【中身】
$s$を増やしながら$i+j+k=s$の状態数をカウントしていき,その合計がはじめて$K$を超えるときの値が$K$番目のケーキの$i+j+k$の値です.コード中では,状態数を加える代わりに,$K$から減じています(cnt +=とする代わりにK -= cntとしている).

$i,j,k$を1ずらして

\begin{aligned}
0\leq i,j,k \leq N-1
\end{aligned}
で考えます.

$0\leq s \leq 3(N-1)$に対して

\begin{aligned}
i+j+k = s
\end{aligned}
となる$(i,j,k)$の組み合わせの総数は
  1. $0\leq s\leq N-1$の場合:$s$個の○と2個の|の並べ方で決まるので,$\begin{pmatrix}s+2 \\ 2\end{pmatrix}=\dfrac{(s+2)(s+1)}{2}$通り
  2. $N\leq s \leq 2N-1$の場合:上と同じですが,$i,j,k$のいずれかが$N$以上となる場合を除く必要があります.これは,$s$から$N$除いた上で組み合わせを求めた後に$N$を$i,j,k$のいずれかに振り分けることで求められます($0\leq s-N \leq N-1$).よって,$\begin{pmatrix}s+2 \\ 2\end{pmatrix} - 3\cdot \begin{pmatrix}s-N+2 \\ 2\end{pmatrix}$通りです.
  3. $2N \leq s \leq 3(N-1)$の場合:$N$以上となるのが1つの場合と2つの場合があります.上と同様に$N$を確保して考えると,$N$以上となるのが2つの場合に「確保した$N$」と「確保してない$N$」の役割を逆にしたものをダブルカウントしています.これは,あらかじめ$2N$確保して,3つのうち2つに配分することを考えれば算出できるので,足し戻すことで正しい組み合わせが求められます.よって,$\begin{pmatrix}s+2 \\ 2\end{pmatrix} - 3\cdot \begin{pmatrix}s-N+2 \\ 2\end{pmatrix}+\begin{pmatrix}3 \\ 2\end{pmatrix}\begin{pmatrix}s-2N+2 \\ 2\end{pmatrix}$通りです.


(公式解説京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) - YouTube)のように,包除原理で考えたほうがわかりやすいかもしれません.1つ以上が$N$以上となるものを除き,2つ以上が$N$以上となるものを加え,...といった具合です.つまり,条件を満たさないものは,$A_{i}=\{i \mid i \notin [0,N-1]\}$に対して

\begin{aligned}
&|A_{i}\cup A_{j} \cup A_{k}| \\
&=|A_{i}| + |A_{j}| + |A_{k}| \\
&\quad - |A_{i}\cap A_{j}| - |A_{j}\cap A_{k}| - |A_{k}\cap A_{i}| \\
&\quad + |A_{i}\cap A_{j}\cap A_{k}| \\
&=3\cdot \begin{pmatrix}s-N+2 \\ 2\end{pmatrix} \\
&\quad - 3\cdot \begin{pmatrix}s-2N+2 \\ 2\end{pmatrix} \\
&\quad + \begin{pmatrix}s-3N+2 \\ 2\end{pmatrix}
\end{aligned}
と計算できます.


同様に,各$i\in\{0,1,...,N-1\}$を増やしながら$i+j+k=s$を満たす状態数$\mathrm{c}$をカウントしていき,はじめて$K$を超えるときの値として,$i=x$の値を決定します.$j$の値を決めれば,$k=s-j$と決まってしまうので,$j$に$\{0,1,...,N-1\}$を入れる方法が状態数です.

  • $0 \leq s - x \leq N-1$の場合:$\{0,1,…,s-x\}$の$s-x+1$が状態数です.
  • $N\leq s-x \leq 2(N-1)$の場合:$\{(s-x)-(N-1), …, N-1\}$の$N-1-(s-x-(N-1)) + 1$通り.
  • $2(N-1) < s-x \leq 3(N-1)$の場合:$0$通り.


最後に,$j=y$を決めれば$k$は自動的に決まります.そこで,$j\in\{0,1,...,N-1\}$を増やしながら,$k$が矛盾しないように決められる($0\leq k = s-(x+y) \leq N-1$)のであればカウントを増やしていきます(あるいはKを減らすK -= 1).$K=0$となる$x,y$が答えになります.


以上,元のコードとは考え方を少し変えてしまったので,修正版をおいておきます(スペースなど汚いですが).PyPy3でないとTLEでした.

N, K = map(int, input().split())

def tri(n):
    return (n+2) * (n + 1) // 2

for s in range(3 * (N - 1) + 1):
    if s <= N - 1:
        cnt = tri(s)
    elif s <= 2*N-1:
        cnt = tri(s) - 3*tri(s-N)
    else:
        cnt = tri(s) - 3*tri(s-N) + 3*tri(s-2*N)
    if K <= cnt:
        for x in range(N):
            if 0<= s-x <= N - 1:
                c = s-x+1
            elif N<= s-x <= 2 * (N - 1):
                c = 2*N - s+x-1
            else:
                c = 0
            if K <= c:
                for y in range(N):
                    if 0 <= s-(x + y) <= N-1:
                        if K == 1:
                            print(x + 1, y + 1, s - x - y + 1)
                            exit(0)
                        K -= 1
            K -= c
    K -= cnt


F - Minflip Summation