キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) A～C問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
株式会社キーエンス様について
キーエンス様は、FA（ファクトリー・オートメーション）総合メーカーとして、FA用センサをはじめ、3D測定器、画像処理装置、デジタルマイクロスコープなど、 付加価値の高い商品を通じて、生産現場の生産性・品質の向上に大きく貢献しています。
平均年収がバカ高いことで有名ですね。
興味のある学生の方は新卒採用ページをご覧ください。
A - Last Card
ABCのA問題は10回に1回くらいやたら難しい問題が出ます。今回がそのやたら難しい回なので、今回解けなかった人も落ち込まずに競技プログラミングを続けてください。
公式解説の通り、
(A+K-1)を計算して出力、ただし結果が「0」ならば「N」へ変換して出力する
という方法で解けます。
【提出1】
これを思いつかなかった場合は、カードを作ってN人にK回配ってしまえばいいです。
まず以下のように書くことでN枚のカードを作れます。
cycle=list(range(A,N+1))+list(range(1,A))
N：3
K：3
A：2
であれば
cycle=[2,3,1]
となります。
1枚目は人2、2枚目は人3、3枚目は人1へ配られることを表しています。
これをたくさんつなげます。
cycle=cycle*1000
cycle=[2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,...]
という形になります。
あとはfor文を使ってK回カードを配っていきます。
最後に配ったカードが誰に配られたのか、記録して出力すればOKです。
【提出2】
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出1】
# 入力の受け取り
N,K,A=map(int,input().split())
# (A+K-1)をNで割った余り
ans=(A+K-1)%N
# ansが「0」ならば
if ans==0:
# Nを出力
print(N)
# そうでないなら(「0」以外なら)
else:
# ansを出力
print(ans)
【提出2】
# 入力の受け取り
N,K,A=map(int,input().split())
# 配るカードを順番に並べる
cycle=list(range(A,N+1))+list(range(1,A))
# 大量につなげる(*(数字)が大きすぎるとMLEするので注意！)
cycle=cycle*1000
# K回配る
for i in range(K):
# 配っているカード
card=cycle[i]
# 最後に配られたカードを出力
print(card)
B - KEYENCE building
a,bを正の整数として、4ab+3a+3bとしてあり得る数を列挙します。
Sは最大でも1000なので、a,bともに1000以下の範囲を探索すればよいです。
実装では余裕を持って1～(1000より少しだけ大きな数)までfor文で確認すればよいでしょう。
そして予想した面積があり得る数に含まれるか？を順番に確認していきます。
xがリストに含まれるか？は
if x in (リスト):
で判定できます。
今回は含まれないか？が知りたいのでnotをつけて
if x not in area:
となります。
【提出】
# 入力の受け取り
N=int(input())
S=list(map(int,input().split()))
# あり得る面積のパターン
area=[]
# a=1~1009(1000より大きければなんでもOK)
for a in range(1,1010):
# b=1~1009(1000より大きければなんでもOK)
for b in range(1,1010):
# 4ab+3a+3bを計算して追加
area.append(4*a*b+3*a+3*b)
# 予想が間違っている人の人数
count=0
# i=0~(N-1)まで
for i in range(N):
# i番目の予想
x=S[i]
# 予想があり得る面積になければ
if x not in area:
# カウント+1
count+=1
# 答えの出力
print(count)
C - ABC conjecture
A,Bが決まればCの個数はすぐわかります。
B≤C≤(N/AB)
になるので、((N/AB)の切り捨て-B+1))個です。
あり得るA,Bを全部試すとしてどこまで探索すればよいか考えましょう。
まずAは最大で3√N(Nの3乗根)となることがわかります。それより大きければA=B=Cの場合でもNを超えてしまうからです。
実装では
N<A**3
となったら終了とします。
次にBです。Aは決まっているとして、Bは最大で√(N/A)までとなります。それより大きければB=Cの場合でもNを超えてしまうからです。
実装では
N/A<B**2
となったら終了(次のAへ)とします。
Nの最大値は10^11です。TLEしないのか不安になりますが、計算量はO(N^(2/3))となりますのでぎりぎり間に合います。
(N=10^11の場合、31857094(≒10^7)回の計算を行います)
公式解説にもあるように調和級数を計算していけばこの計算量を得られるのですが少々ややこしいです。
計算量解析をするよりも、とりあえず通りそうなコードを書いてみて、「コードテスト」でpypyを選んでテストしてみるのがいいでしょう。
pythonではもちろん間に合わないのでpypyで提出します。
【提出】
# pypyで提出
# 入力の受け取り
N=int(input())
# 答えのカウント
ans=0
# A=1~(10^6-1)まで
for A in range(1,10**6):
# N<A^3なら
if N<A**3:
# ループを終了
break
# B=A~(10^6-1)まで
for B in range(A,10**6):
# (N/A)<B^2なら
if N/A<B**2:
# ループを終了 次のAへ
break
# あり得るCの数=(N/(A*B))の切り捨て-B+1
ans+=int(N/(A*B))-B+1
# 答えの出力
print(ans)
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
1～24問目まではサンプルとして無料公開しています
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
【kindle】
【booth(pdf】