NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
日本電気株式会社（NEC）様について
コンテストのトップページから
「なぜNECがプログラミングコンテストを実施するのか」
「リサーチエンジニアの業務内容」
を確認できます。
また『2021年10月～12月下旬に、学生の皆さんを対象としたイベント「中央研究所 見学交流会（修士／博士対象）」をオンラインで開催します！』とのことなので、興味がある方はご確認ください。
A - First Grid
問題文が長くてややこしくてうんざりしますが頑張って読みましょう。
条件をしっかり確認すると「No」になるパターンは以下の2つだけであることがわかります。
黒マスが左上と右下
S1：#.
S2：.#
黒マスが右上と左下
S1：.#
S2：#.
ifを使ってS1,S2がこのどちらかになっているか確認し、条件分岐します。
どちらでもなければ「Yes」となります。
「Yes」「No」は文字列なので出力の際、"Yes","No"とダブルクオーテーションをつけてください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
S1=input()
S2=input()
# 黒マスが左上と右下
if S1=="#." and S2==".#":
# 「No」を出力
print("No")
# 黒マスが右上と左下
elif S1==".#" and S2=="#.":
# 「No」を出力
print("No")
# それ以外
else:
# 「Yes」を出力
print("Yes")
B - Hard Calculation
各桁の足し算が一つでも10以上であれば「Hard」、全て9以下であれば「Easy」となります。
各桁計算して確かめましょう。
実装の手順は以下です。
(1)A,Bは文字列で受け取る
数値で受け取ると各桁の計算が面倒です。
(2)A,Bはひっくり返す
例えばA=1234、B=54321の場合(A,Bの桁数が違う場合)
A[0]=1=千の位
B[0]=5=万の位
となって桁がずれます。
そこでA=4321、B=12345とひっくり返します。そうすると
A[0]=4=一の位
B[0]=1=一の位
となるので後の実装が楽になります。
文字列をひっくり返すときは
文字列[::-1]
と書きます。よく使う書き方ですが「python 文字列 反転」などでググると出てくるのでいちいち覚える必要はありません。
(3)桁数の小さい方がいくらかを確認する
例えばA=1234、B=54321の場合、Aは4桁、Bは5桁です。この場合は4桁だけ確認すればOKです。
桁数=文字数なので、Aの桁数はlen(A)、Bの桁数はlen(B)です。
桁の小さい方を確認するときは
min(len(A),len(B))
と書けば良いです。
(4)各桁の足し算を確認する
A,Bのi桁目はそれぞれA[i],B[i]となります。
このままでは文字列扱いとなってしまい、足し算ができません。そこでintを使って整数へ変換してから足し算します。
int(文字列)
と書くことで文字列→整数へ変換できます。
あとは(3)で確認した桁数回足し算して確認すればOKです。
(5)足し算が一つでも10以上なら「Hard」を出力して終了
途中でプログラムを終了する場合は
exit()
と書きます。
全て9以下なら「Easy」を出力します。
【提出】
# 入力を文字列で受け取り
A,B=map(str,input().split())
# ひっくり返す
A=A[::-1]
B=B[::-1]
# 桁数の小さい方
keta=min(len(A),len(B))
# i=0~(桁数の小さい方)
for i in range(keta):
# i桁目を整数へ変換
A_int=int(A[i])
B_int=int(B[i])
# 各桁の足し算が10より大きければ
if 10<=A_int+B_int:
# 繰り上がりがある
# 「Hard」を出力
print("Hard")
# 終了
exit()
# 繰り上がりなし
# 「Easy」を出力
print("Easy")
C - Cheese
貪欲法を使います。
貪欲法はきちんと説明すると難しいのですが、大雑把に 「前後の状況は考えずに今一番良いものを取り続ける方法」 と覚えてください。
詳しく知りたい人はWikipediaをご覧ください。
この問題では単純に美味しさの大きいチーズから可能な限り載せ続ければ良いです。
まずチーズの情報を美味しさが大きい順に並び替えます。
リストを大きい順に並び替えるには以下のように書きます。
(リスト).sort(reverse=True)
そしてチーズの情報を確認し、残り載せられる重さをWとして
・チーズの重さ≤Wなら→全部載せる
・W<チーズの重さなら→W[g]分載せる
とします。
【提出】
# 入力の受け取り
N,W=map(int,input().split())
# チーズの情報
cheese=[]
# N回
for i in range(N):
# 入力の受け取り
A,B=map(int,input().split())
# 情報の格納
cheese.append([A,B])
# 美味しさの大きい順にソート
cheese.sort(reverse=True)
# 答え
ans=0
# i=0～(N-1)まで
for i in range(N):
# i種類目のチーズの美味しさ
delicious=cheese[i][0]
# i種類目のチーズの重さ
weight=cheese[i][1]
# 重さ≤Wなら
if weight<=W:
# 全部載せる
ans+=delicious*weight
# 載せられる残りの重さ
W-=weight
# そうでないなら(W<重さなら)
else:
# W[g]分載せる
ans+=delicious*W
# forを抜ける
break
# 答えの出力
print(ans)
D - Longest X
尺取法を使います。
例として以下の入力を考えます。
S：XX...X.X.X.
K：2
まず 「区間[左,右]について全て「X」とすることはできるか？」 から考えましょう。
つまり区間[左,右]について、その区間の「.」を全て「X」に変えられるか？ということを考えます。
例えば区間[5,9]だと「5≤i≤9についてS[i]を全てXにできるか」=「Sの5～9番目を全てXにできるか」ということです。
※ただしSは0インデックス、すなわち先頭をS[0]=0番目、次をS[1]=1番目、...と数えます。
[5,9]について「.」を全て「X」に変えられるか？を考えるならS[5]～S[9](「X.X.X」)に含まれる「.」の数を数えればよいです。
「.」の数がK以下ならば変えられます。(「.」の数は2個、K=2なので変えられる)
ところがS[5]はなにか,S[6]はなにか,...と一個一個「X」か「.」か確認していては当然TLEします。
そこで累積和を使います。
以下のように「0～i番目までに含まれる「.」の数をカウントするリスト」を作ります。名前はcountです。
i番目までの「累積」の「.」の数を数えているので「累積和」です。
累積和を使うと区間に含まれる「.」の数を簡単に計算できます。
具体的には以下のように計算します。
・左=0の場合
[左,右]に含まれる「.」の数=count[右]
・それ以外の場合(1≤左)
[左,右]に含まれる「.」の数=count[右]-count[左-1]
[5,9]であれば
[5,9]に含まれる「.」の数=count[9]-count[5-1]=count[9]-count[4]=5-3=2となります。
S[5]～S[9]=「X.X.X」ですから確かに「.」の数は2個です。
countは以下の計算で作ります。
・count[0]
S[0]=「X」の場合：count[0]=0
S[0]=「.」の場合：count[0]=1
・count[i](1≤i)
S[i]=「X」の場合：count[i]=count[i-1]
S[i]=「.」の場合：count[i]=count[i-1]+1
S[i]が「X」ならひとつ左の要素をそのまま持ってくる、「.」ならばひとつ左の要素+1とするというイメージです。
これで区間[左,右]に対して高速で「.」の数を求めることはできました。
しかし全ての[左,右]の区間を確認するとSの長さをNとしてO(N^2)かかるのでやはりTLEします。
そこで尺取法を使います。
よくよく考えてみると[左,右]について順に確認する時、右は戻る必要がありません。
例えば
「[1,5]の区間は「.」を全て「X」に変えられる」
となっていれば
「[1,3]の区間は「.」を全て「X」に変えられる」
ということが自動的にわかります。つまり右については5より小さい数を確認する必要はないということです。
よって右は5より大きい数、すなわち[1,6],[1,7],...を確認すればよいです。
この考えをベースに以下の手順で計算、確認します。
(1)「答え」を0とする
(2)右=0とする
(3)左=0～N-1まで順に増やす
(4)[左,右]が全て「X」に変えられるか計算する
・変えられる
右をプラス1
・変えられない
[左,右-1]の長さ(全て「X」に変えられた区間の長さ)を計算→「答え」より長い区間なら「答え」を更新
次の左へ((2)へ戻る)
左と右の動き方が尺取り虫のようなので、この方法を 「尺取法」 と呼びます。
実装にはforとwhileを使います。
慣れるまで少し難しく感じると思いますが、尺取法はよく使う割にみんな苦手なのでできるとレートが上がりやすいです。頑張りましょう。
【提出】
# 入力の受け取り
S=input()
K=int(input())
# Sの長さ
N=len(S)
# 「.」の累積個数
count=[0]*N
# S[0]が「.」ならば
if S[0]==".":
# count[0]に1を入れる
count[0]+=1
# i=1~(N-1)まで
for i in range(1,N):
# S[i]=「X」ならば
if S[i]=="X":
# 一つ左と同じ
count[i]=count[i-1]
# そうでないなら(S[i]=「.」)
else:
# 一つ左+1
count[i]=count[i-1]+1
# 答え
ans=0
# 右
right=0
# left=0~(N-1)まで
for left in range(N):
# right<Nの間
while right<N:
# もし左が0なら
if left==0:
# [左,右]にある「.」の数=count[right]
sum_section=count[right]
# そうでないなら(1≤左)
else:
# [左,右]にある「.」の数=count[right]-count[left-1]
sum_section=count[right]-count[left-1]
# [左,右]にある「.」の数≤Kならば
# ⇔[左,右]にある「.」を全て「X」に変えられるなら
if sum_section<=K:
# 右を移動
right+=1
# そうでないなら([左,右]にある「.」を全て「X」に変えられないなら)
else:
# whileを抜ける
break
# [左,右-1]の長さを計算し、今までの答えより大きければ更新
ans=max(ans,right-left)
# 答えの出力
print(ans)
E - Graph Destruction
UnionFindを使います。
UnionFindはグループ分けを高速でできるデータ構造です。
具体的には以下のことができます。
・a,bを同じグループとする⇔a,bを連結する：【O(logN)くらい】(厳密には違いますがO(logN)くらいと思っておけばOKです)
・a,bが同じグループか判定する⇔a,bが連結か確認する：【O(1)くらい】(厳密には違いますがO(1)くらいと思っておけばOKです)
とにかくめちゃくちゃ速く上記2つができるデータ構造だと覚えましょう。
きちんとした説明はAtCoder公式が解説スライドを作っているのでそちらを御覧ください。
UnionFindの実装はかなり難しいです。ですが問題を解くのにそこまで理解する必要はなく、以下の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()
【初期化時の注意事項】
本問のように頂点の番号が1から始まる場合、
初期化：変数名=UnionFind(N+1)
としなければならないことに注意してください。
このクラスは頂点番号が0インデックスでの使用を想定しているためです。
【使用例】
# 初期化：変数名=UnionFind(要素の数)
UF=UnionFind(10)
# グループ化：変数名.merge(要素番号1,要素番号2)
UF.merge(0,2)
UF.merge(1,3)
UF.merge(3,0)
# 根の確認：変数名.leader(要素番号)
leader_x=UF.leader(1)
# 同一グループかの確認：変数名.same(要素番号1,要素番号2)
if UF.same(1,5)==True:
print("同一グループ")
else:
print("別グループ")
# 所属するグループのサイズ確認：変数名.size(要素番号)
size_x=UF.size(1)
# グループ全体の確認：変数名.groups()
print(UF.groups())
「連結」という言葉が出てきたときはだいたいUnionFindで解けます。
しかしUnionFindに頂点や辺を削除する機能はありません。できるのは
・頂点をつなげる
・頂点同士がつながっているか確認する
の2つです。
そこで逆順で考えます。
つまり頂点Nまで消された何もない状態から、頂点N,頂点N-1,...を順に戻していくと考えます。
まず入力を受け取る時、通常無向グラフではA→B,B→A両方へ進めるとします。
が、頂点を番号の大きい順に戻していくので、A→B(小→大)へは進めてもB→A(大→小)へは進めないです。(頂点Bを戻した時点では頂点Aはまだ戻っていません)
よってA→Bの有向グラフとして入力を受け取ります。
※条件にAi<Biがあることに注意してください
頂点を1個戻すとその時点で連結成分が1個増えます。
戻した頂点から進める頂点についてUnionFindで連結かどうか？を確認します。
・連結でない場合
頂点同士をつなげる⇔同じグループとする。
同じグループになったから連結成分が1個減る。
・連結の場合
すでにつながっているなので何もしなくて良い。
このように各頂点の情報を確認しながら連結成分の数を増やしたり減らしたりして記録していきます。
UnionFindのより詳細な説明、クラスの内容の解説については拙著『AtCoder 凡人が『緑』になるための精選50問詳細解説』に記載しています。
内容までしっかり理解しておきたいという人は購入をご検討ください。
詳細は本ページ下部【広告】を御覧ください。
【提出】
# 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!=[]]
# 入力の受け取り
N,M=map(int,input().split())
# 辺の情報
connect=[[] for i in range(N+1)]
# M回
for i in range(M):
# 入力の受け取り
A,B=map(int,input().split())
# A→Bへ辺が張れる
connect[A].append(B)
# UnionFindを定義
UF=UnionFind(N+1)
# 答えの格納用
ans=[0]*(N+1)
# 現在の連結成分の数
count=0
# i=N~1まで
for i in range(N,0,-1):
# 頂点iを追加
# 連結成分が一つ増える
count+=1
# 頂点x=頂点iと結ばれる頂点
for x in connect[i]:
# 頂点iと頂点xが連結でないなら
if UF.same(i,x)==False:
# 頂点iと頂点xをつなげる
UF.merge(i,x)
# 連結成分が一つ減る
count-=1
# 答えを格納
ans[i-1]=count
# i=1~Nまで
for i in range(1,N+1):
# 答えの出力
print(ans[i])
【広告】
『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】