ABC206(AtCoder Beginner Contest 206) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
Panasonic様について
本コンテストはパナソニック株式会社〔Panasonic Corporation〕様がスポンサードされています。
興味のある方は以下の採用情報ページを御覧ください。
A - Maxi-Buying
Nを受け取り、1.08Nを計算して切り捨てし、206と大小比較する、という方法でも解けますがおすすめしません。
少数の計算を行うと誤差が出る場合があります。この問題は出題者側が意図的に数字を選んで1.08Nを計算する方法でも正解となるようにしています。
少数の計算を行う必要がある場合はまずそれを避けられないか？から考えましょう。
本問の場合、以下のように場合分けできます。
N<191：206円より安い(Yay!)
N=191：206円(so-so)
191<N：206円より高い(:()
上記条件をif文で書き、それぞれに当てはまるものを出力すればOKです。
「Yay!」、「so-so」、「:(」は文字列ですから、
print(Yay!)
ではなく
print("Yay")
と""をつけなければならないことに注意してください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
N=int(input())
# N<191の場合
if N<191:
# Yay!を出力
print("Yay!")
# N=191の場合
elif N==191:
# so-soを出力
print("so-so")
# それ以外(191<N)の場合
else:
# :(を出力
print(":(")
B - Savings
i日目に貯金箱へいくら入っているか、for文で1日ずつ実際に計算すればOKです。
貯金額がN以上となった時点で「i」を出力し、プログラムを終了します。
(exit()で終了できます)
【提出】
# 入力の受け取り
N=int(input())
# 貯金額
money=0
# i=1~10**6
for i in range(1,10**6):
# i日目 i円を貯金箱へ
money+=i
# 貯金額がN以上ならば
if N<=money:
# iを出力
print(i)
# 終了
exit()
C - Swappable
組み合わせの数は全部でNC2=N(N-1)/2となります。Nが大きいので全ての組を確認することはできません。
全部の組み合わせからAi=Ajとなるような組み合わせの数を引きましょう。
Ai=Ajとなるような組の数はAにある要素がいくつ含まれているかを確認すれば計算できます。
例として以下の入力を考えます。
「入力例」
7
1 2 1 2 2 3 4
Nは7なので組み合わせ全部の数は7C2=21通りです。
さらにそれぞれの要素がいくつあるか数えます。
1：2個
2：3個
3：1個
4：1個
「1」は2個あります。Ai=Ajとなる選び方は2C2=2*(2-1)/2=1なので1組あります。
(A1とA3)
「2」は3個あります。Ai=Ajとなる選び方は3C2=3*(3-1)/2=3なので3組あります。
(A2とA4,A2とA5,A4とA5)
「3」、「4」は1個しかないのでAi=Ajとなる選び方はありません。
よって
21-1-3＝17
17組が答えとなります。
実装では連想配列(defaultdict)を使って各要素の個数をカウントします。
(リストで管理するとサイズが最大10^9のリストが必要となり、MLE(メモリ制限超過)します)
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]
詳しく知りたい人は以下を参照してください。
連想配列(count)でそれぞれの要素をカウントしたあとは、記録した要素(x)それぞれについてxC2を計算して全組み合わせから引きます。
for x in count.values():
と書くことでcountの値それぞれを順にxへ格納して処理ができます。
【提出】
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# defaultdictのインポート
from collections import defaultdict
# 要素の出現回数を数える連想配列countを用意
count=defaultdict(int)
# Aのそれぞれの要素(a)について
for a in A:
# aの出現回数を+1
count[a]+=1
# 全組み合わせ=N*(N-1)//2
ans=N*(N-1)//2
# countの値(x)それぞれについて
for x in count.values():
# Ai=Ajとなる組の数x*(x-1)//2を引く
ans-=x*(x-1)//2
# 答えの出力
print(ans)
D - KAIBUNsyo
UnionFindを使います。
左端と右端から順に値が同じか確認していきますがxがyに置き換えられてーということを管理するやり方では間に合いません。
x,yを置き換える⇔x,yを同じグループとする
と考えます。
例として以下の入力を考えます。
「入力例」
8
1 4 1 2 4 3 3 2
(1)左端から0個目(A1：1)と右端から0個目(A8：2)
1と2は現状違うグループですから、違う数です。これらを同じグループとします。
同じグループになった数は同じ数とみなされます。
グループ①：1,2
(同じグループにする⇔グループのどれかの数に置き換えている、と考えています。この場合は2を1に置き換えています)
操作回数：1
(2)左端から1個目(A2：4)と右端から1個目(A7：3)
4と3は現状違うグループですから、違う数です。これらを同じグループとします。
同じグループになった数は同じ数とみなされます。
グループ①：1,2
グループ②：3,4
(置き換えで言うと3を4に置き換えています)
操作回数：2
(3)左端から3個目(A3：1)と右端から3個目(A6：3)
1と3は現状違うグループですから、違う数です。これらを同じグループとします。
ここではグループ①にグループ②を統合しましょう。これによりグループ②に含まれる4もグループ①に含まれます。
同じグループになった数は同じ数とみなされます。
グループ①：1,2,3,4
(置き換えで言うと3を1に置き換えています。ここまでで4は3に置き換わっていますから、4→3→1と1に置き換わります。よって2,3,4は全て1に置き換わっています)
操作回数：3
(4)左端から4個目(A4：2)と右端から4個目(A5：4)
2と4は同じグループです。ゆえに操作の必要はありません。
操作回数：3
以上より必要な操作回数は3回です。
このグループ管理をUnionFindで行います。
UnionFindはグループ分けを高速でできるデータ構造です。
具体的には以下のことができます。
・a,bを同じグループとする：O(logN)くらい(厳密には違いますがO(logN)くらいと思っておけばOKです)
・a,bが同じグループか判定する：O(1)くらい(厳密には状況により違いますがO(1)くらいと思っておけばOKです)
とにかくめちゃくちゃ速く上記2つができるデータ構造だと思えば良いです。
きちんとした説明はAtCoder公式が解説スライドを作っているのでそちらを御覧ください。
実装はかなり難しいです。ですが問題を解くのにそこまで理解する必要はなく、以下のUnionFindクラスをコピペして使えればOKです。
# UnionFindを用意
class UnionFind:
def __init__(self,n):
self.n=n
self.parent_size=[-1]*n
def leader(self,a):
if self.parent_size[a]<0: return a
self.parent_size[a]=self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self,a,b):
x,y=self.leader(a),self.leader(b)
if x == y: return
if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y]=x
return
def same(self,a,b):
return self.leader(a) == self.leader(b)
def size(self,a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result=[[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r!=[]]
上記をコードの最初にコピペしてから以下のように使います。
・初期化：変数名=UnionFind(要素の数)
・根の確認：変数名.leader(要素番号)
・グループ化：変数名.merge(要素番号1,要素番号2)
・同一グループかの確認：変数名.same(要素番号1,要素番号2)
(同一ならTrue,違うグループならFalseを返す)
・所属するグループのサイズ確認：変数名.size(要素番号)
・グループ全体の確認：変数名.groups()
【使用例】
# 初期化：変数名=UnionFind(要素の数)
UniFi=UnionFind(10)
# グループ化：変数名.merge(要素番号1,要素番号2)
UniFi.merge(0,2)
UniFi.merge(1,3)
UniFi.merge(3,0)
# 根の確認：変数名.leader(要素番号)
leader_x=UniFi.leader(1)
# 同一グループかの確認：変数名.same(要素番号1,要素番号2)
if UniFi.same(1,5)==True:
print("同一グループ")
else:
print("別グループ")
# 所属するグループのサイズ確認：変数名.size(要素番号)
size_x=UniFi.size(1)
# グループ全体の確認：変数名.groups()
print(UniFi.groups())
本問で使うのは
・初期化：変数名=UnionFind(要素の数)
・グループ化：変数名.merge(要素番号1,要素番号2)
・同一グループかの確認：変数名.same(要素番号1,要素番号2)
の3つです。
x,yが同一グループでない⇔same(x,y)==False
と確かめることができます。
今回提出したコードについては、UnionFindの初期化について要素数を10^6と大きめにしています。
実際は必要分(Aの最大値+1)で初期化してもOKです。
UnionFindのより詳細な説明、クラスの内容の解説については拙著『AtCoder 凡人が『緑』になるための精選50問詳細解説』に記載しています。
内容までしっかり理解しておきたいという人は購入をご検討ください。
詳細は本ページ下部【広告】を御覧ください。
【提出】
# UnionFind
class UnionFind:
def __init__(self, n):
self.n=n
self.parent_size=[-1]*n
def merge(self, a, b):
x, y=self.leader(a), self.leader(b)
if x == y: return
if abs(self.parent_size[x])<abs(self.parent_size[y]): x, y=y, x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y]=x
return
def same(self, a, b):
return self.leader(a) == self.leader(b)
def leader(self, a):
if self.parent_size[a]<0: return a
self.parent_size[a]=self.leader(self.parent_size[a])
return self.parent_size[a]
def size(self, a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result=[[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r!=[]]
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# UnionFind 要素数10^6で初期化
Uni=UnionFind(10**6)
# 答えを格納する変数
ans=0
# i=0~N//2まで
for i in range(N//2):
# 左側
A_left=A[i]
# 右側
A_right=A[N-i-1]
# 左側と右側が違うグループなら
if Uni.same(A_left,A_right)==False:
# 答えに+1
ans+=1
# 同じグループへ
Uni.merge(A_left,A_right)
# 答えを出力
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】