AtCoder Beginner Contest 161 感想&反省[For Beginners]

AtCoder Beginner Contest 161 が2020/04/04に行われました。みなさんお疲れ様でしたー。

今回はA,B,C問題を3完。Performanceも668と、茶色パフォーマンスでした。

解説

A問題

https://atcoder.jp/contests/abc161/tasks/abc161_a

いろいろな解法があります。

時間のかかる解法になりますが、3つの数字をリスト(配列)と捉え、問題文通りに実装すればよさそうです。

A = list(map(int,input().split()))
A[0],A[1] = A[1],A[0]
A[0],A[2] = A[2],A[0]
print(*A)
#豆知識 (*リスト名)とすると、リストの
要素を全て出力することが出来ます

B問題

https://atcoder.jp/contests/abc161/tasks/abc161_b

問題文通り実装すればよさそうです。

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = sum(A)*(1/(4*M))
ans = 0
for i in range(N):
if A[i]>=B:
ans += 1
if ans >= M:
print("Yes")
else:
print("No")

C問題

https://atcoder.jp/contests/abc161/tasks/abc161_c

数学の問題です。始めに、

$N = K$
$N ＜ K$
$N ＞ K$

の3つのパターンでそれぞれどうするかを考えます。

1. $N = K$ の場合

$N - K$ をすると、絶対値は $0$ になり、その後は $0→K→0→K$ を繰り返すので

$0$ を出力しましょう。

2. $N ＜ K$ の場合

例えば、 $N = 3,K = 7$ の場合。 $4→3→4→3 \dots$ となり、

$N = 2,K = 6$ の場合、 $4→2→4→2 \dots$ となります。

つまり、 $abs(N-K)$ が $N$ の最小値といえそうです。

ただし、これには例外があり、 $2N＜K$ の場合は、 $N$ が最小値となります。

3. $N ＞ K$ の場合

$N = 7, K = 3$ の場合 $4→1→2→1 \dots$

$N = 11, K = 3$ の場合 $8→5→2→1→2 \dots$

となります。つまり、 $K-(N \% K)$ が $N$ の最小値といえそうです。

ただし、場合によっては $N \% K$ が $N$ の最小値となる場合があるので

$min(K-(N \% K),N \% K)$ を出力すればどちらのケースでも対応できます。

あとはこれを実装すればよいです。

N,K = map(int,input().split())
if N==K:
print(0)
elif N > K:
if N%K == 0:
print(0)
else:
print(min(N%K,K-(N%K)))
elif N < K:
if 2*N<K:
print(N)
else:
print(abs(N-K))

D問題はどう見ても数学っぽいので飛ばしました。

E問題

https://atcoder.jp/contests/abc161/tasks/abc161_e

この問題、解けそうな感じがしたのでTryしてみました(解説ではありません)

まずは、テストケースを見てみます。

入力例 1 Copy

Copy

11 3 2
ooxxxoxxxoo ooxxxoxxxoo

出力例 1 Copy

Copy

高橋君は $11$ 日間のうち $3$ 日働こうとしています。ある日働いたらその後 $2$ 日間は働きません。

働く日としてありえる組み合わせは「 $1, 6, 10$ 日目」「 $1, 6, 11$ 日目」「 $2, 6, 10$ 日目」「 $2, 6, 11$ 日目」の $4$ 通りです。

したがって、 $6$ 日目に必ず働きます。

ここで考えたのは、"x"の数の累積和を利用して解くというものです。

(Sのi文字目をS[i]とします)

ooxxxoxxxoo という文字列があった時に、S[i]までの"x"の文字列の数をそれぞれ計算していきます。

すると、[0,0,1,2,3,3,4,5,6,6,6]という配列が完成しました。

働ける日の条件として

1日働いたら $C$ 日は働かない

"x"の書いてある日付では働かない

という条件であるので

S[i]からS[i+C]番目の文字列で

・S[i] = "o"である

・S[i]からS[i+C]までの文字列に含まれる"o"の個数が1個以上ある

という条件に当てはまる日が働ける日の候補　ということで考えてみました。

それからいろいろと実装をしていきました。

すると、なんとサンプルケースに当てはまっていくではありませんか！

提出をしてみたのですがWA。理由が今でもよく分かっていませんorz

N,K,C = map(int,input().split())
S = input()
L = [0]*(N)
ans = 0
P =
for i in range(N):
if S[i] == "x":
ans += 1
L[i] = ans
for i in range(C):
L.append(ans)
Q =
for i in range(N):
flag = 0
if S[i] == "o":
#もし1日目で働ける場合
if L[i+C]-L[i] <= C:
#累積の休み日数がC以下
P.append(i+1)
else:
if len(P) >= 1:
s = P.copy()
Q.append(s)
P.clear()
else:
if len(P) >= 1:
s = P.copy()
Q.append(s)
P.clear()
Q.append(P)
if len(Q) == K:
for i in range(len(Q)):
if len(Q[i]) == 1:
print(*Q[i])

以上、A問題～C問題の解説と、E問題の考察でした。

今回を含め、以降の記事ではPython3で書いたコードをここにまとめることにします。

(Githubでも良かったのですがブログ上に貼り付ける方が便利なので)

ちなみに、今日21:00から行われる　Judge System Update Test Contest 202004は、

unratedのコンテストです。(順位表から、4問なので　おそらく旧ABC級？)

も　し　か　す　る　と First Accepted (FA)を取れる機会にもなりそうなので、FA取りたい人は1番を目指して頑張って下さい！

(ペナルティはつきますがratedでは無いので関係ないと思います)

Ruteのプログラミング日記

競技プログラミング(AtCoder)の問題の解説や、過去問を解いた感想、また解けない過去問について共有したいと思ってます。

AtCoder Beginner Contest 161 感想&反省[For Beginners]

入力例 1 Copy

出力例 1 Copy