ABC318 A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
A
難しく考えず、問題の通りにM,M+P,M+2P,...がN以下になっているかを順番に確認すればOKです。
つまりx=0,1,2,...に対してM+xPがN以下になっているかを確認します。
xを順番に増やしていくという処理はforかwhileで実装できますが、どちらかというとforの方が理解しやすいと思います。
for文は
for 変数 in range(最後の数+1):
と書きます。
x=0,1,2,...と増やしていくなら以下のようになります。
for x in range(999999999999):
「999999999999」というのは単に大きめの数字を指定しているだけで特に意味はありません。
実際は制約の最大値2*10^5を超えていればOKです。
あとは
・M+xP≦N ならば 満月を見れたのでカウントを増やす
・そうでない(N<M+xP) ならば 答えを出力して処理を終了する
というようにします。
途中で終了するときはexit()と書きます。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
N,M,P=map(int, input().split())
# 満月を見れた回数
count=0
x=0,1,2,...
for x in range(999999999999):
# M+xP≦Nならば
if M+x*P<=N:
# カウントを増やす
count+=1
# そうでなければ
else:
# 答えの出力
print(count)
# 終了
exit()
B
ちゃんと計算して面積を求めにいくと大変です。
制約からシートが掛けられるのは0≦x≦100、0≦y≦100の範囲であることはわかります。
ですのでこの領域を1*1の正方形1万個に分割し、それぞれの正方形がシートに覆われているかを順番に確認していきましょう。
具体的には正方形の真ん中の点を覆うようなシートがあるか確認していくという方法が楽です。
例えば一番左下の正方形((0,0),(0,1),(1,0),(1,1)で作られる)であれば(0.5,0.5)が真ん中の点です。
どれかのシート、つまりどれかのiについて
Ai<0.5<Bi
かつ
Ci<0.5<Di
となっていればこの正方形はシートに覆われていると言えます。そのため面積を1カウントします。
同じ処理を(0.5,1.5),(0.5,2.5),...,(0.5,99.5),(1.5,0.5),(1.5,1.5),(1.5,2.5),...,(99.5,99.5)について1万回やればOKです。
【提出】
# 入力の受け取り
N=int(input())
# 情報の格納用
ABCD=[]
# N回
for i in range(N):
# 入力の受け取り
A,B,C,D=map(int, input().split())
# 二次元配列へ格納
ABCD.append([A,B,C,D])
# 面積
Space=0
# x=1~100
for x in range(1,101):
# y=1~100
for y in range(1,101):
# A,B,C,Dに要素を順に代入
for A,B,C,D in ABCD:
# 真ん中の点がシートに覆われていたら
if A<x-0.5<B and C<y-0.5<D:
# 面積にカウント
Space+=1
# 次の点へ
break
# 答えの出力
print(Space)
C
D日毎に1日周遊パスを買ったほうが安くなるか確認していきます。
以下の例で考えます。
N,D,P：5 2 10
F：7 1 6 3 6
まずFを大きい順に並び替えましょう。
F：7 6 6 3 1
Dは2なので最初の2個、すなわち7 6を考えます。
7+6=13ですが、P=10なのでここでは周遊バスを買ったほうがお得です。
次の2個は6 3です。
6+3=9で、P=10なのでここはパスを買わずに一日ごとに支払います。
大きい順に並べたので、これ以降は必ず一日ごとに支払った方がお得なのですが、分岐を作ると処理が面倒です。
以降も都度D個の和とPどちらが大きいか比較して安い方を取るというやり方にするのが楽です。
制約は大きくないのでD個ごとに毎回和を計算しても十分間に合います。
【提出】
# 入力の受け取り
N,D,P=map(int, input().split())
F=list(map(int, input().split()))
# 大きい順に並び替え
F.sort(reverse=True)
# 支払金額
pay=0
# 初期値
i=0
# D*i<Nの間
while D*i<N:
# Pと(FのD*i～(D*(i+1)-1)までの和)のうち小さい方を足す
pay+=min(P,sum(F[D*i:D*(i+1)]))
# 次のiへ
i+=1
# 答えの出力
print(pay)
D
まず用語を確認しておきましょう。
「重み付き」
辺ごとに重み、つまり数字が割り振ってあるということです。
「無向」
向きがない、つまりA→B、B→Aどちら向きにも進めるということです。
(今回はあまり関係ありません)
「完全グラフ」
どの2つの頂点を選んでもそれらを結ぶ辺があるということです。
辺を選ぶというのは要するに端点の2つを選ぶということです。
そして端点が相異なるという条件から一度選んだ端点は別のものと組み合わせることは出来ません。
例えばN=4の場合、頂点(1,2)を選んだら(1,3)や(2,3)は選べず、残りは(3,4)だけになります。
組み合わせをリストで表すことを考えます。
例えば[1,3,2,4]ならば前から2つずつに分けて(1,3)と(2,4)の辺を取り、その重みを合計するというような形です。N=4の場合ありうる組は以下の3つだけです。
[1,2,3,4]
[1,3,2,4]
[1,4,2,3]
ではN=16の場合、この組み合わせはいくつあるでしょうか。
考え方としては
1番目は残っているもので最も小さいものを選ぶ(=1)
2番目は残っているものから好きなものを選ぶ(=2,3,4,...,16)
3番目は残っているもので最も小さいものを選ぶ
4番目は残っているものから好きなものを選ぶ
...
としていくことです。
1,3,5,...,15番目は固定、2,4,6,...,16番目は残っているものを選択するので、
1*15*1*13*1*11*...*1=2027025通りとなります。ちょっと多いですがpypyなら間に合うかなーくらいですね。
Nが奇数のときは選ばない頂点を1個選択し、残りの頂点で同じように考えます。
ではこれをどうやって実装するか考えます。
まず入力の受け取りですが、Dをそのまま使うとちょっとややこしいので二次元の表形式にしてしまいましょう。
例えば
D=
1 5 4
7 8
6
であれば以下のような形にします。
具体的なコードは以下のようにします。
# i=1~(N-1)
for i in range(1,N):
# 受け取り
d=list(map(int, input().split()))
# 前に0を(i+1)個追加
d=[0]*(i+1)+d
# Dへ追加
D.append(d)
# N行目を作る
D.append([0]*(N+1))
# i=1~N
for i in range(1,N+1):
# k=1~N
for k in range(1,N+1):
# コピー
D[k][i]=D[i][k]
わざわざここまでしなくても解くことはできますが、わかりやすいほうがいいですね。
次に組み合わせのリストを作る方法ですが、これはDFS(深さ優先探索)を使います。
情報を管理するために2つのリストを使います。
Pair：頂点の組み合わせリスト。前から2つずつペアにするという意味。
Used：頂点がすでに組み合わせのリストに入っているか管理するリスト。例えばUsed[1]=Trueなら1がすでにPairへ入っていることを意味する。
Usedが全てTrueになったら全ての頂点がPairに入ったということですから、ペアの内容から重みを計算していきます。
そうでなければ
奇数番目はまだPairに入っていない頂点のうち最も小さいもの(Used[x]=Falseとなっているxのうち最も小さいもの)
偶数番目は残っている頂点全てを順にペアに入れていきます。
本問はDFS、再帰関数の実装としては比較的難しい問題です。
DFSをやったことがない人は本問の前に簡単なDFS問題で練習することをおすすめします。ABC213Dがおすすめです。
ABC213D：https://atcoder.jp/contests/abc213/tasks/abc213_d
解説：https://qiita.com/sano192/items/f4e7c64184714dce6ebf#d---takahashi-tour
解説動画もあるのでそちらもぜひご覧ください。
【提出】
#pypyで提出
# 再帰回数上限を10^6へ変更(再帰関数を使うときはとりあえず書いておく)
import sys
sys.setrecursionlimit(10**6)
# 入力の受け取り
N=int(input())
# Dに0行目を作る
D=[[0]*(N+1)]
# i=1~(N-1)
for i in range(1,N):
# 受け取り
d=list(map(int, input().split()))
# 前に0を(i+1)個追加
d=[0]*(i+1)+d
# Dへ追加
D.append(d)
# N行目を作る
D.append([0]*(N+1))
# i=1~N
for i in range(1,N+1):
# k=1~N
for k in range(1,N+1):
# コピー
D[k][i]=D[i][k]
# 各頂点がUsedに入っているかを確認するリスト
Used=[False]*(N+1)
# 0はTrueにしておく
Used[0]=True
# ペアのリスト
Pair=[]
# 答え
ans=0
# DFSをする関数
def DFS(Used):
# ansを更新できるように
global ans
# Usedが全てTrue⇔全ての頂点がPairに入った
if all(Used)==True:
# 重み合計のカウント
count=0
# i=0~(N//2-1)
for i in range(0,N//2):
# ペアの重みを計算して足す
count+=D[Pair[2*i]][Pair[2*i+1]]
# 答えを更新
ans=max(count,ans)
# そうでなければ
else:
# x=UsedがFalseになっている頂点のうち、最も小さいもの
x=Used.index(False)
# k=(x+1)~N
for k in range(x+1,N+1):
# kがまだPairに入っていなければ
if Used[k]==False:
# x,kを追加
Pair.append(x)
Pair.append(k)
# 追加したことを記録
Used[x]=True
Used[k]=True
# 次のDFSへ
DFS(Used)
# x,kをPairから取り出し
Pair.pop()
Pair.pop()
# 取り出したことを記録
Used[x]=False
Used[k]=False
# Nが偶数なら
if N%2==0:
# そのままスタート
DFS(Used)
# Nが奇数なら(選ばない頂点を一つ決めておく)
else:
# i=1~N
for i in range(1,N+1):
# Used[i]をTrueに⇔Pairに入れないようにする
Used[i]=True
# DFSをする
DFS(Used)
# 戻す
Used[i]=False
# 答えの出力
print(ans)
E
とりあえずてきとうな例を作って考えてみましょう。
A：1 2 1 3 2 3 2 2 4 3 2
インデックスを振るとこんな感じです。
この問題は同じ2つの数字の間に、違う数字が何個あるか数えてくださいという意味です。
例えば1番目の「2」と7番目の「2」の間には1,3,2,3,2があります。この5個のうち2と違うのは1,3,3の3つなので、(i,j,k)の組は3つ作れるわけです。((i,j,k)=(1,2,7),(1,3,7),(1,5,7))
もうちょっと賢く式にすると
(大きい方のインデックス)-（小さい方のインデックス)-(間にある同じ数字の個数)-2+1
となります。1番目の「2」と7番目の「2」であれば
7-1-2-2+1=3
となります。
「2」が存在するのは1,4,6,7,10番目です。
(i,k)のそれぞれの組と、その計算を書いてみます。
縦方向にそれぞれの個数を確認すると以下のようになります。
+1：0個
+4：1個
+6：2個
+7：3個
+10：4個
-1：4個
-4：3個
-6：2個
-7：1個
-10：0個
-0：4個
-1：3個
-2：2個
-3：1個
-2：10個
+1：10個
規則性が見えてきました。
「2」で言えば
1つ目のインデックス番号1について+1が0個,-1が4個
2つ目のインデックス番号4について+4が1個,-4が3個
3つ目のインデックス番号6について+6が2個,-6が2個
4つ目のインデックス番号7について+7が3個,-7が1個
5つ目のインデックス番号10について+10が4個,-10が0個
と足した上で
-0を4個
-1を3個
-2を2個
-3を1個
-4を0個(※これを入れたほうが実装が楽)
更に
-2：10個
+1：10個
ですがこれは合計して
-1：10個
としましょう。この10個というのは行数なので5C2=5*(5-1)//2と計算すればOKです。
他の「1」「3」「4」についても同様に存在するインデックス番号を確認し、同じ計算をして全部足せば終わりです。
各要素のインデックス番号はdefaultdictでリスト管理するのが楽です。
defaultdict(連想配列)について
連想配列は別名「辞書」とも言い、「キー」と対応する「値」を登録できるデータ構造です。
pythonでは標準で搭載されており、dict()と書くことで使えます。
しかし標準のものはデフォルトの値(初期値)が設定できず、存在しない「キー」にアクセスする可能性があるときの処理が面倒です。
defaultdictは標準の連想配列と同様に使えて、さらに初期値を設定できます。
値の割当が行われていない「キー」には自動的に初期値が割り振られます。
「使い方」
・インポート：from collections import defaultdict
・作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
・キー、値の登録【O(1)】：変数名[キー]=値
・値の参照【O(1)】：変数名[キー]
# インポート：from collections import defaultdict
from collections import defaultdict
# 作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
AsArray=defaultdict(int)
# キー、値の登録【O(1)】：変数名[キー]=値
# キー、値ともに数値、文字列、タプルを入れることが可能
# ただしリストをキーにすることはできない
AsArray[1]=10
AsArray["Men"]="Taro"
AsArray[(1,2)]=[3,4,5]
# 値の参照【O(1)】：変数名[キー]
print(AsArray[1])
print(AsArray["Men"])
print(AsArray[(1,2)])
# 値が割当されていないキーも参照可能(値はデフォルト値)
print(AsArray[99])
【提出】
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# defaultdictをインポート
from collections import defaultdict
# 初期値は空のリスト
indx=defaultdict(list)
# i=0~(N-1)
for i in range(N):
# 各要素のインデックス番号を記録
indx[A[i]].append(i)
# 「X」を両端(Ai,Ak)としたときの組み合わせ数を確認する関数
def indxCount(X):
# リストの長さ
n=len(X)
# 組み合わせ数
count=0
# i=0~(n-1)
for i in range(n):
# +X[i]がi個
count+=X[i]*i
# -X[i]が(n-i-1)個
count-=X[i]*(n-i-1)
# i=0~(n-1)
for i in range(n):
# -iが(n-i-1)個
count-=i*(n-i-1)
# -1がnC2=n*(n-1)//2個
count-=n*(n-1)//2
# 値を返す
return count
# 答え
ans=0
# Xlist：indxの値を順に代入
for Xlist in indx.values():
# 答えにプラス
ans+=indxCount(Xlist)
# 答えの出力
print(ans)