ABC200参戦記

AtCoder Beginner Contest 200の参加記録です。
切りの良い開催数で京セラさんが主催してくれているコンテストです。

そういえば私、十数年前に京セラさんの面接受けに行ったことありましたね。

セラミックのことほとんど知らなかったので、面接受ける前にセラミックの勉強をしたことを思い出しました。

見事、お祈りされましたけど。
(お祈りメールすら来なかったような気もするな・・・当時はそういうところが多かったような気がします。)

こんな懐かしいようなことを思い出しながら参加したABC200のC問題までを、私が理解した内容で振り返ります。

私はレートは600前後のユーザで、使用言語はPython3です。python3のACコード付きです。

A – Century

標準入出力と除算、if文が書けるかの問題として解きました。

100年で次の世紀になるので、100で割った整数部分の数を計算できれば基本的にOKです。

C=N//100 として、

Nが100で割り切れる年はCを出力。100で割り切れない場合はC+1が答えになります。

割り切れるかどうかの判定は余りを計算すればよく、Python3では R=N%100 としたRが余りになります。

# 京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）
# A - Century

N=int(input())

ans=N//100
if N%100==0:
    print(ans)
else:
    print(ans+1)

公式解説を見て、もっと賢い方法もあることを知りました。

西暦に99を足して100で割った整数で求めたい世紀がわかるのですね。

1行で書くとこれでもACします。

print((int(input())+99)//100)

読みやすいかどうかは別として、こういうコードが書ける人すごいと思います。

B – 200th ABC-200

for文が書けるかを問われる問題。数の末尾に特定の数を付け加えたいときの操作については、データの型の取り扱いを問われる問題として解きました。

問題文に書いてある通りに実装していけば基本的にOKな問題ですね。

200で割り切れる場合は良いとして、200で割り切れない場合の操作については、以下の2種類の方法があります。

1. 一度、今の数字を文字列とみなして、文字列”200″を連結させる。その後、もう一度数字として取り扱えるようにする。
2. 今の数字を1,000倍する。その数に200を足す。

私は1の方法で実装しました。

# 京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）
# B - 200th ABC-200

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

for i in range (K):
    if N%200==0:
        N//=200
    else:
        N=str(N)+str(200)
        N=int(N)
print(N)

2の方法のほうが綺麗なように感じます。文字列への変換と再度、整数型への変換で無駄に時間がかかるのは、ABC174-C Repsept で理解したはずなのに、また同じことをやってしまいました。今回は実行回数が多いわけではないので問題ありませんでしたが、こういう変換も少しずつ慣れていきたいですね。

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

for i in range (K):
    if N%200==0:
        N//=200
    else:
        N*=1000
        N+=200
print(N)

C – Ringo’s Favorite Numbers 2

倍数判定と場合の数の問題。

書いてあることを愚直に実装すると、2重のfor文となってしまい、TLEします。

XがYの倍数かどうかの判定は、X％Y==0か否かで判定可能です。

言われてみれば当たり前のようにも思いますが、今までの生活では意識していなかったです。

ということは、

Ai – Aj が200の倍数になるということは、Ai -Aj を200で割った余りが0になることです。

つまり、

Ai – Aj ≡ 0 (mod200)

上記の合同式が成り立つということで、

Ai ≡ Aj (mod200)

となるAi, Aj を見つければよいことがわかります。

合同式については、高校数学の美しい物語 さんのサイトや、鈴木貫太郎さんのYouTube動画、よびのりたくみさんの動画、古賀さんの動画などが参考になると思います。

mod200 の配列を用意して、それぞれのAi をその配列に格納していきます。この際、あとで使うのは個数だけなので、個数が入るようにしていきます。

標準入力の受け取りから、mod200の配列を作成するところまでは以下の通りです。

N=int(input())
As=list(map(int,input().split()))

mod200=[0]*200

for i in range (N):
    d=As[i]%200
    mod200[d]+=1

ここからは、条件を満たす組の数を求めていきます。

これは、nこの中から2個選ぶ場合の組み合わせ数なので、_nC₂ で求まりますね。

nが2の場合は1、nが3の場合は3、nが4の場合は6となります。

_nC₂ の場合は、プログラムで表現するのも楽で、n>=2 で、n*(n-1) を2で割ればOKです。

これらの組み合わせの数を答え用の変数に加算していけばAC出来ます。

# 京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）
# C - Ringo's Favorite Numbers 2

N=int(input())
As=list(map(int,input().split()))

mod200=[0]*200

for i in range (N):
    d=As[i]%200
    mod200[d]+=1
# print(mod200)

ans=0
for m in mod200:
    if m>1:
        ans+=(m*(m-1))//2
print(ans)

今回のC問題が比較的スムーズに解けるようになったのは、AtCoderの公式解説や上記3名のYouTubeのおかげです。