パナソニックグループプログラミングコンテスト2022(ABC251) A~C問題の解説記事です。
灰色~茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
更新時はツイッターにて通知します。
https://twitter.com/AtCoder4
パナソニックグループについて
本コンテストはパナソニックグループ様が主催されています。
社内競プロerにインタビューした記事は以下から御覧ください。
学生の方にはインターンシップ募集もされています。
興味がある方は以下のリンクを御覧ください。
A - Six Characters Dif:9
・文字数が1の場合
Sを6個くっつけて出力します。
・文字数が2の場合
Sを3個くっつけて出力します。
・上記以外(文字数が3の場合)
Sを2個くっつけて出力します。
これらの条件をifで書きます。
文字列をくっつけるのは単純に「+」で結べばOKです。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
S=input()
# 文字数が1の場合
if len(S)==1:
# Sを6個くっつけて出力
print(S+S+S+S+S+S)
# 文字数が2の場合
elif len(S)==2:
# Sを3個くっつけて出力
print(S+S+S)
# それ以外(文字数が3の場合)
else:
# Sを2個くっつけて出力
print(S+S)
B - At Most 3 (Judge ver.) Dif:181
おもりを3個以下選ぶということなので、「1個選ぶ」「2個選ぶ」「3個選ぶ」パターンに分けて考えましょう。
実装に合わせ0インデックス、すなわちA1をA[0]、A2をA[1]、...ANをA[N-1]と呼びます。
選んだおもりの合計の重さを記録していき、最終的に重さの種類数を出力します。
・1個選ぶ場合
要するにA[0]~A[N-1]を順番に選んで重さを記録すれば良いわけです。
重さを記録するとき、リストに記録していくと同じ重さでも重複して記録されてしまいます。
そこで重複した要素を記録しないsetを使います。setの名前はans_setとしましょう。
setに追加するときはappendではなくaddを使うことに注意してください。
# おもりを1個選ぶ場合
# i=0~(N^1)
for i in range(N):
# 重さがW以下ならば
if A[i]<=W:
# セットに記録
ans_set.add(A[i])
・2個選ぶ場合
A[0]とA[1]
A[0]とA[2]
...
A[1]とA[2]
A[2]とA[3]
...
A[N-2]とA[N-1]
という組を順に作ります。
以下のように書けば(i,j)=(0,1),(0,2),...,(1,2),(1,3),...,(N-2,N-1)という組を作ることができます。
for i in range(N):
for j in range(i+1,N):
ループがどう進むか見てみましょう。
まずi=0からスタートです。i=0に対してj=i+1,i+2,...となるので(0,1),(0,2),...(0,N-1)が作れます。
次にi=1です。i=1に対してj=i+1,i+2,...となるので(1,2),(1,3),...(1,N-1)が作れます。
以下はi=2,i=3,...とループが進み、全ての組を作れるというわけです。
競技プログラミングでは二重ループを非常によく使います。
二重ループは息をするように書けるようになりましょう。
# おもりを2個選ぶ場合
# i=0~(N^1)
for i in range(N):
# j=(i+1)~(N-1)
for j in range(i+1,N):
# 重さの合計がW以下ならば
if A[i]+A[j]<=W:
# セットに記録
ans_set.add(A[i]+A[j])
・3個選ぶ場合
A[0]とA[1]とA[2]
A[0]とA[1]とA[3]
...
A[0]とA[2]とA[3]
A[0]とA[2]とA[4]
...
A[1]とA[2]とA[3]
A[1]とA[2]とA[4]
...
A[N-3]とA[N-2]とA[N-1]
という組を順に作ります。
二重ループの応用で三重ループを作りましょう・
以下のように書けば(i,j,k)=(0,1,2),(0,1,3),...,(0,2,3),(0,2,4),...,(1,2,3),(1,2,4),...(N-3,N-2,N-1)という組を作ることができます。
for i in range(N):
for j in range(i+1,N):
for k in range(j+1,N):
同じようにループがどう進むか見てみましょう。
まずi=0からスタートです。i=0に対してj=i+1ですから最初はj=1となります。
更にj=1に対してk=j+1,j+2,...となるので(0,1,2),(0,1,3),...(0,1,N-1)が作れます。
次はj=2に進みます。k=j+1,j+2,...となるので(0,2,3),(0,2,4),...(0,2,N-1)が作れます。
この処理がj=3,4,...と進んでいき、jが終わったらまたiが増え...となり、いい感じに組が作れます。
# おもりを3個選ぶ場合
# i=0~(N^1)
for i in range(N):
# j=(i+1)~(N-1)
for j in range(i+1,N):
# k=(j+1)~(N-1)
for k in range(j+1,N):
# 重さの合計がW以下ならば
if A[i]+A[j]+A[k]<=W:
# セットに記録
ans_set.add(A[i]+A[j]+A[k])
作れる重さの記録ができたらans_setの要素数が答えです。
len(セット)でセットの要素数が出力できます。
【提出】
# 入力の受け取り
N,W=map(int,input().split())
A=list(map(int,input().split()))
# 重さの種類を記録していくセット
ans_set=set()
# おもりを1個選ぶ場合
# i=0~(N^1)
for i in range(N):
# 重さがW以下ならば
if A[i]<=W:
# セットに記録
ans_set.add(A[i])
# おもりを2個選ぶ場合
# i=0~(N^1)
for i in range(N):
# j=(i+1)~(N-1)
for j in range(i+1,N):
# 重さの合計がW以下ならば
if A[i]+A[j]<=W:
# セットに記録
ans_set.add(A[i]+A[j])
# おもりを3個選ぶ場合
# i=0~(N^1)
for i in range(N):
# j=(i+1)~(N-1)
for j in range(i+1,N):
# k=(j+1)~(N-1)
for k in range(j+1,N):
# 重さの合計がW以下ならば
if A[i]+A[j]+A[k]<=W:
# セットに記録
ans_set.add(A[i]+A[j]+A[k])
# 種類数=setの長さを出力
print(len(ans_set))
C - Poem Online Judge Dif:246
各文字列についてまず今までに出てきていないか(=オリジナルか?)を確認します。
オリジナルであればそれまでの最高得点と比較し、点数が上回っていたら更新する、という方法で解きます。
今までに出てきていないか? を今までに出てきた文字列一つずつ確認していく、という方法ではO(N^2)となってTLEします。
defaultdictを使ってすでに出てきた文字列を記録、確認していきましょう。
連想配列(defaultdict)を使ったことがない人は以下を参照してください。
defaultdict(連想配列)について
辞書または連想配列と言います。
キー:値
というような対応付を行えるデータ構造です。
連想配列はdict()と書くことでも使えますが、デフォルトの値(初期値)が設定できません。そのため存在チェックなど色々面倒が発生します。
その面倒を避けるためにdefaultdictを使います。
import:from collections import defaultdict
作成(デフォルト0):変数名=defaultdict(int)
キー、値の登録:変数名[キー]=値
値の取り出し:変数名[キー]
【使用例】
# インポート
from collections import defaultdict
# 作成(デフォルト0):変数名=defaultdict(int)
dictionary=defaultdict(int)
# キー、値の登録:変数名[キー]=値
dictionary[5]=1
# 値の取り出し:変数名[キー]
x=dictionary[5]
詳しく知りたい人は以下を参照してください。
文字列をキーとして、まだ出てきていないものは0(デフォルト値)、すでに出てきた文字列は1と記録していきます。
記録するdefaultdictの名前をS_Existとします。
【例】
S_Exist["aaa"]=0
S_Exist["bbb"]=1
「aaa」は0なのでまだ出てきていません(オリジナル)
「bbb」は1なのですでに出てきた文字列です(オリジナルでない)
まだ出てきていない文字列であればそれまでの最高得点と比較し、点数が上回っていたら更新する、としていきます。
最後に答えを出力します。
【提出】
# 入力の受け取り
N=int(input())
# defaultdictをインポート
from collections import defaultdict
# すでに出てきた文字列を記録する
# デフォルト値は0
S_Exist=defaultdict(int)
# 答えの番号
ans_No=0
# それまでの最高得点
ans_Point=0
# i=1~N
for i in range(1,N+1):
# 入力の受け取り(文字列で受け取り)
S,T=map(str,input().split())
# Tを整数へ変換
T=int(T)
# もしまだ出てきていないならば
# ⇔0(デフォルト値)が記録されていたら
if S_Exist[S]==0:
# 出てきた文字列として1を記録
S_Exist[S]=1
# それまでの最高得点を上回っていたら
if ans_Point<T:
# 答えの番号を更新
ans_No=i
# 最高得点を更新
ans_Point=T
# 答えの出力
print(ans_No)
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段:100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/
【booth(pdf)】
https://sano192.booth.pm/items/3179185
1~24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf
『AtCoder ABC201~225 ARC119~128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif:0~1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える?】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段:300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV
【booth(pdf)】
https://booth.pm/ja/items/3698647
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段:200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/
【booth(pdf)】
https://sano192.booth.pm/items/3698668
『AtCoder ABC226~250 ARC129~139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif:0~1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える?】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段:300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS
【booth(pdf)】
https://sano192.booth.pm/items/4025713
ARC129~139の部分のみ抜粋した廉価版 もあります。
値段:200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF
【booth(pdf)】
https://sano192.booth.pm/items/4025737
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です!
マクロ、VBAが全くわからない人でも大丈夫! 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます!
値段:300円(Kindle Unlimited対象)
サンプルとして「準備」~「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb
【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW
【booth(pdf】
https://sano192.booth.pm/items/3785312