A~Cに回答できました.
すごい解説:
- A - Century
- B - 200th ABC-200
- C - Ringo's Favorite Numbers 2
- D - Happy Birthday! 2
- E - Patisserie ABC 2
- F - Minflip Summation
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ずらして
0\leq i,j,k \leq N-1
\end{aligned}
$0\leq s \leq 3(N-1)$に対して
i+j+k = s
\end{aligned}
- $0\leq s\leq N-1$の場合:$s$個の○と2個の|の並べ方で決まるので,$\begin{pmatrix}s+2 \\ 2\end{pmatrix}=\dfrac{(s+2)(s+1)}{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}$通りです.
- $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]\}$に対して
&|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