目指せ水色コーダー！！！！！！
ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。
こちらの記事の初中級者が解くべき過去問精選 100 問
をPythonで解いていきます！
@e869120さんに感謝！！！！！！
###過去記事リンク
全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
全探索：順列全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】
二分探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】
深さ優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】
幅優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】
(2020/05/07 追記)
※補足
この100問解いてみたシリーズの(Part6)の記事から、入力を
input()→sys.stdin.readline().rstrip()
に変えています！
【Python】競プロテンプレ【AtCoder】
テンプレ用の記事も作ったので、よかったら使ってください〜
#「Part2」〜工夫する全列挙編〜
以下の5問を解いていきます！
#####全探索：工夫して通り数を減らす全列挙
5 AtCoder Beginner Contest 095 C - Half and Half
6 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
7 JOI 2007 本選 3 - 最古の遺跡 面白いです。Python3 だと想定解法が TLE する可能性があります。（PyPy3 であれば間に合う場合が多いです）
8 Square869120Contest #6 B - AtCoder Markets 全探索すると無数に通り数があるように見えますが、ひとつ工夫すると現実的な通り数で全列挙できる問題です。
9 JOI 2008 予選 4 - 星座探し
5 AtCoder Beginner Contest 095 C - Half and Half
Difficulty:220
「AB ピザ」を0枚からMAX(A,B)枚まで全部調べればいいですね！
def LI(): return list(map(int,input().split()))
A,B,C,X,Y = LI()
ans = float('INF')
for i in range(max(X,Y)+1):
price = A*max(X-i,0)+B*max(Y-i,0)+C*2*i
ans = min(ans,price)
print(ans)
「A ピザ」がマイナス枚にならないように、0との最大値というのがコツ！
もちろん「B ピザ」も同じ！)
A*max(X-i,0)
#6 三井住友信託銀行プログラミングコンテスト
Difficulty:836
暗所番号「000〜999」までの1000通りしかないので、1000通り調べればいいね！
str.zfill()は文字を0詰めしてる！
for in range(10)の3重for文でもOKだけど、なるべくネストを減らしてコードを見やすく書いてバグを減らそう！
def I(): return int(input())
N = I()
S = input()
ans = 0
for i in range(1000):
num = str(i).zfill(3)
if S.find(num[0])==-1:
continue
S1 = S[S.find(num[0])+1:]
if S1.find(num[1])==-1:
continue
S2 = S1[S1.find(num[1])+1:]
if S2.find(num[2])==-1:
continue
ans += 1
print(ans)
#7 JOI 2007 本選 3 - 最古の遺跡
初見で解けませんでした！
難しい！！！！！！
でも非常に勉強になりました！！！！！！
この問題の解説記事書いてたら、やたら長くなったのでw
単体で解説記事を作りました！！！
↓解説はこちら！！！
【Python】JOI 2007 本選 3 - 最古の遺跡(①高校数学ベクトル、②「in リスト」は激遅)【AtCoder】
ACコードだけ貼り付けておきます〜
def I(): return int(input())
def TI(): return tuple(map(int,input().split()))
n = I()
xy = [TI() for _ in range(n)]
set_xy = set(xy)
ans = 0
for i in range(n):
x1,y1 = xy[i]
for j in range(i+1,n):
x2,y2 = xy[j]
vectorx,vectory = x2-x1,y2-y1
if (x1-vectory,y1+vectorx) in set_xy and (x2-vectory,y2+vectorx) in set_xy:
ans = max(ans,vectorx**2+vectory**2)
print(ans)
#8 Square869120Contest #6 B - AtCoder Markets
これも初見で解けなかった！
解説見たら、
s,t の候補は 𝑎1, 𝑎2, 𝑎3, … , 𝑎𝑁, 𝑏1, 𝑏2, 𝑏3, … , 𝑏𝑁 のいずれか
これは、入力例 2, 3 あたりで推測できそう
気づかなかったよ！！！
確かに、入出力2,3もこんなに丁寧に説明してくれているということは
よく考えたらすごいヒントだよなぁ・・・
でも逆にこのカラクリがわかってしまえば、全探索するだけなので難しくない！
list(zip(*A))は行列の転置
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = [LI() for _ in range(N)]
T_A = list(zip(*A))
ans = float('INF')
for x in T_A[0]:
for y in T_A[1]:
temp = 0
for z in A:
temp += abs(z[0]-x)
temp += z[1]-z[0]
temp += abs(z[1]-y)
ans = min(ans,temp)
print(ans)
(2020/04/23 追記)
ちなみに多重for文は、
こちらのサイト
よりitertools.product()を使うと、ネストが一段減って可読性が上がりそう！
itertools.product()を使うと一つのループで複数のリストのすべての組み合わせを取得でき、多重ループと同様の結果が得られる。
これ便利！かつ読みやすい！
全探索で使えそう！
複雑なコードになればなるほど真価を発揮しそう！
今後積極的に使っていこうと思った！
import itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = [LI() for _ in range(N)]
T_A = list(zip(*A))
ans = float('INF')
for x,y in itertools.product(T_A[0],T_A[1]):
temp = 0
for z in A:
temp += abs(z[0]-x)
temp += z[1]-z[0]
temp += abs(z[1]-y)
ans = min(ans,temp)
print(ans)
#9 JOI 2008 予選 4 - 星座探し
7問目の最古の遺跡問題と似てる！
1日目、4時間くらいかけてもACとれなくて少し諦めかけたけど、
2日目、7問目の最古の遺跡問題と同じ構想でやればいけるはず！
と思い直してやってみたら案外すんなりACとれた！！！
やったぜ！
ベクトルの引き算とかやりまくって、添字だらけでわかりずらくなりそうだったので、
勉強もかねてNumpyを使ってみました！
Numpyのすごいところは、ベクトル同士や行列同士の足し算・引き算とかが添字とか使わずそのままで計算きちゃうところだよね！
(ただしNumpyを使っても実行速度はむしろ、普通に実装した時よりかなり遅いw
無理して使うべきではなかったかも・・・
この問題はNumpy使ってACとれたけど、
7問目の最古の遺跡問題では、同じようにNumpy使うとTLE・・・実装の仕方がよくないのかもしれないが)
import numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def solve():
M = I()
Mxy = np.array(sorted([LI() for _ in range(M)]))
N = I()
Nxy = np.array(sorted([LI() for _ in range(N)]))
Mvector = []
for i in range(1,M):
Mvector.append(Mxy[i]-Mxy[0])
if M==1:
return Nxy[0]-Mxy[0]
for i in range(N):
for j in range(i+1,N):
Nvector = Nxy[j]-Nxy[i]
if tuple(Nvector) != tuple(Mvector[0]):
continue
for x in Mvector[1:]:
if not (Nxy[i]+x==Nxy).all(axis=1).any():
break
else:
return Nxy[i]-Mxy[0]
print(*solve())
7問目の最古の遺跡問題では、
①異なる2点間の差からできる1つのベクトルに対して、xとyを入れ替えてどちらかにマイナスをつけた垂直ベクトルを求めて、
②2点からそれぞれ垂直ベクトルを書いてみて、その先の点が2つとも候補にあったら
面積を出す(答えの候補になる)という考え。
似たような考えで
今回の問題では、
①一番初めの点Mxy[0]を基準として、すべての点との差のベクトル一覧を求める(Mvectorのこと)
②異なる2点間の差からできる1つのベクトルについて、Mvector[0]と一致しているベクトルを見つける
③Mvector[0]の基準点Nxy[i]から他のMvectorのベクトルを書いてみて、その先の点がすべて候補にあったら、もともとの星座を並行していることが確定！
④Mvector[0]の基準点Nxy[i]-初めの基準点Mxy[0]
が答え！！！という考え。
ここまで整理できれば、
あとは実装するだけ！！！！！！！！！！！！
コードの細かい補足をすると、
if M==1:
return Nxy[0]-Mxy[0]
M==1のとき、Mvectorは存在しないので、
Mvector[0]などでエラーになってしまう！のでその対策。
if tuple(Nvector) != tuple(Mvector[0]):
Nvectorは、ndarray型
Mvector[0]は、リスト型
なので単純比較できなくて(単純比較しようとするとエラー)、タプルにしてから比較しました！
(ちなみに、ndarrayのndとは、N-dimensional array、多次元配列のことだそうです！ふーん)
for x in Mvector[1:]:
if not (Nxy[i]+x==Nxy).all(axis=1).any():
break
else:
return Nxy[i]-Mxy[0]
elseは、一度もbreakしなかった時だけ流れる！
これ結構便利！！！
また、(Nxy[i]+x==Nxy).all(axis=1).any():
この部分、Nxy[i]+x in Nxyと書きたいんだけどダメ！(この問題はたまたまACにはなっちゃうけどw)。
(x,y)←これが存在していれば、Trueとしたいけど、
Numpyは要素でTrue,Falseを判定するので、
例えばNxyのx座標だけ一致してy座標が一致していなかった場合、
(True,False)となるが、要素に1つでもTrueがあったら、
if Nxy[i]+x in Nxy:←これ自体がTrueになってしまう・・・
（↑実際に動かしたら、何言ってるかわかると思うw）
よって、
行単位で全てTrue→(True,True)となるベクトルが1つ以上存在するか？
=>(Nxy[i]+x==Nxy).all(axis=1).any():
という複雑な書き方になってしまった・・・
7問目の最古の遺跡問題、set_Nxyみたいなのを作った方がわかりやすいか。
ここが少しネックになるし、実行時間(計算量)も良くないので
無理してNumpy使わなくてよかったかも・・・
(2020/05/03 追記)
Numpyなしバージョンのコードも載せておきます・・・
Numpyなしの方が、実行時間が桁違いに早かった・・・
Numpyは使いどころを見極めて使うことにします・・・
import itertools
def I(): return int(input())
def TI(): return tuple(map(int,input().split()))
def solve():
M = I()
Mxy = sorted([TI() for _ in range(M)])
N = I()
Nxy = sorted([TI() for _ in range(N)])
set_Nxy = set(Nxy)
Mvector = []
for i in range(1,M):
Mvector.append((Mxy[i][0]-Mxy[0][0],Mxy[i][1]-Mxy[0][1]))
if M==1:
return (Nxy[0][0]-Mxy[0][0],Nxy[0][1]-Mxy[0][1])
for Nxy1,Nxy2 in itertools.combinations(Nxy,2):
Nvector = (Nxy2[0]-Nxy1[0],Nxy2[1]-Nxy1[1])
if Nvector != Mvector[0]:
continue
for x in Mvector[1:]:
if not (Nxy1[0]+x[0],Nxy1[1]+x[1]) in set_Nxy:
break
else:
return (Nxy1[0]-Mxy[0][0],Nxy1[1]-Mxy[0][1])
print(*solve())
＜別解＞
こんな解法も・・・
Nxy(候補) - Mxy(本物)を全部計算して、
一番頻度が多かったものが答え！！！
確かに！
import collections,numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
M = I()
Mxy = np.array([LI() for _ in range(M)])
N = I()
Nxy = np.array([LI() for _ in range(N)])
kouho = []
for x in Mxy:
for y in Nxy:
kouho.append(tuple(y-x))
count = collections.Counter(kouho)
print(*count.most_common()[0][0])
次回は、以下の5問を解いていきます！
#####全探索：ビット全探索
10 ALDS_5_A - 総当たり 基本問題です。
11 AtCoder Beginner Contest 128 C - Switches
12 AtCoder Beginner Contest 002 D - 派閥
13 JOI 2008 予選 5 - おせんべい 茶色コーダーにはやや難問ですが解くことをおすすめします。
14 Square869120Contest #4 B - Buildings are Colorful! 工夫も必要で、一筋縄では解けない難問ですが、解けば確実に力がつきます。
Part2/22
おわり！