目指せ水色コーダー！！！！！！
ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。
こちらの記事の初中級者が解くべき過去問精選 100 問
をPythonで解いていきます！
@e869120さんに感謝！！！！！！
関連記事リンク
全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】
全探索：順列全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】
二分探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】
深さ優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】
幅優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】
動的計画法：ナップザック DP
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part8/22】
動的計画法：区間 DP
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part9/22】
動的計画法：bit DP
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part10/22】
動的計画法：その他
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part11/22】
最短経路問題：ダイクストラ法
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part12/22】
最短経路問題：ワーシャルフロイド法
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part13/22】
最小全域木問題
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part14/22】
高速な素数判定法
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part15/22】
高速なべき乗計算
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part16/22】
逆元を使う問題
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part17/22】
累積和
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part18/22】
Union-Find
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part19/22】
その他のテクニック
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part20/22】
実装問題
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part21/22】
数学的な問題
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part22/22】
(2020/05/07 追記)
※補足
この100問解いてみたシリーズの(Part6)の記事から、入力を
input()→sys.stdin.readline().rstrip()
に変えています！
【Python】競プロテンプレ【AtCoder】
テンプレ用の記事も作ったので、よかったら使ってください〜
記念すべき「Part1」〜普通の全列挙編〜
以下の4問を解いていきます！
全探索：全列挙
1 ITP1_7_B - How Many Ways? 基本問題です。
2 AtCoder Beginner Contest 106 B - 105
3 AtCoder Beginner Contest 122 B - ATCoder
4 パ研杯2019 C - カラオケ これが解ければ全探索に慣れたと思って良いです。
1 ITP1_7_B - How Many Ways?
↓過去記事でも類題として取り上げたことのある問題！
(この時は3重for文で解いた！)
【Python】ABC133B(右上三角形問題)【AtCoder】
3重for文で全く問題ないのですが、
今回は気分的に2重for文にしてみた！
def LI(): return list(map(int,input().split()))
while 1:
n,x = LI()
if n==x==0:
break
ans = 0
for i in range(1,n+1):
for j in range(1,n+1):
k = x-i-j #ただし、kの条件は[1,n]
if 1<=k<=n and i<j<k:
ans += 1
print(ans)
(2020/05/01 追記)
今ならこんな感じでコード書く。
import itertools
def LI(): return list(map(int,input().split()))
while 1:
n,x = LI()
if n==x==0:
break
ans = 0
for i,j,k in itertools.product(range(1,n+1),repeat=3):
if i<j<k and i+j+k==x:
ans += 1
print(ans)
itertools.productを使えばネストが深くならない！
ので、3重for文でもわかりやすい。
(2020/05/02 追記)
itertools.combinationsこっちの方がスマートでした！！！
import itertools
def LI(): return list(map(int,input().split()))
while 1:
n,x = LI()
if n==x==0:
break
ans = 0
for i,j,k in itertools.combinations(range(1,n+1),3):
if i+j+k==x:
ans += 1
print(ans)
2 AtCoder Beginner Contest 106 B - 105
Difficulty:66
ほぼ脳死でいけた！
rangeの第3引数(デフォルトは1)を例えば「2」にすると、1個飛ばしになる！
range(1,int(i**0.5)+1)は素数判定や約数探すときに愛用してる！
int()は小数点以下切り捨て！
def I(): return int(input())
N = I()
ans = 0
if N>=105:
for i in range(105,N+1,2):
count_yakusuu = 0
for j in range(1,int(i**0.5)+1):
if i%j==0:
count_yakusuu += 2
if count_yakusuu==8:
ans += 1
print(ans)
(2020/04/20 追記)
ちなみに、AtCoderでは、
ABC162〜Python3のバージョンが3.8まで一気に上がったので、
今後のコンテストは、約数→sympy.divisors()で簡単ですねw
(余談：最大公約数→math.gcd()も使えるようになったし！やった〜)
(2020/05/03 追記)
sympy使えませんでした！
なんか勘違いしてたみたいです・・・ごめんなさい・・・
最大公約数→math.gcd()こっちは使えます！！！
参考コードは一応残しておきます・・・
参考コード
import sympy
def I(): return int(input())
N = I()
ans = 0
if N>=105:
for i in range(105,N+1,2):
if len(sympy.divisors(i))==8:
ans += 1
print(ans)
3 AtCoder Beginner Contest 122 B - ATCoder
Difficulty:85
2通りの解法を思いついた！
1個はいつもの貪欲法。もう1個はDP。
解1(貪欲法)
考えられる答え候補をすべて求めて、ansを上書きしていく！
S = input()
ans,temp = 0,0
for x in S:
if x in 'ACGT':
temp += 1
else:
temp = 0
ans = max(ans,temp)
print(ans)
解2(DP)
enumerateの第2引数(デフォルトは0)をつけると、
インデックスがその数字からスタート！
S = input()
dp = [0]*(len(S)+1) #1_indexed
for i,x in enumerate(S,1):
if x in 'ACGT':
dp[i] = dp[i-1]+1
print(max(dp))
(2020/05/26 追記)
解3(部分文字列の全探索)
重複組み合わせitertools.combinations_with_replacementを使って、
部分文字列の全探索ができる！！！
すごい！！！
import itertools
S = input()
ans = 0
for i,j in itertools.combinations_with_replacement(range(len(S)),2):
if all([x in 'ACGT' for x in S[i:j+1]]):
ans = max(ans,j+1-i)
print(ans)
4 パ研杯2019 C - カラオケ
いやー難しかった！
1問目の右上三角形問題と3問目を組み合わせたような問題。
でも、次からはすらすらとコードが書けるようになった気がする！
def LI(): return list(map(int,input().split()))
N,M = LI()
A = [LI() for _ in range(N)]
ans = 0
for i in range(M):
for j in range(i+1,M):
temp = 0
for k in range(N):
temp += max(A[k][i],A[k][j])
ans = max(ans,temp)
print(ans)
＜別解＞
上のコードには劣る。一番はじめにACを獲得したコード。
for x in Aから始めてしまうと、複雑なコードになってしまう。。。
一時退避用の2次元配列を用意して・・・
行列を入れ替えて足し算・・・
その最大値！
def LI(): return list(map(int,input().split()))
N,M = LI()
A = [LI() for _ in range(N)]
temp = [[0]*(M*(M-1)//2) for _ in range(N)]
for i,x in enumerate(A):
l = 0
for j in range(M):
for k in range(j+1,M):
l += 1
temp[i][l-1] = max(x[j],x[k])
print(max([sum(x) for x in (zip(*temp))]))
(2020/05/01 追記)
Numpyマスター(仮)になった！
ので、今ならこんな感じでコード書く。
import itertools,numpy as np
def LI(): return list(map(int,input().split()))
N,M = LI()
a = np.array([LI() for _ in range(N)])
ans = 0
for i,j in itertools.product(range(M),repeat=2):
if i<j:
ans = max(ans,a[:,[i,j]].max(axis=1).sum())
print(ans)
Numpyになれるとこちらのコードの方が読みやすかったりする。
np.max().sum()と後ろに付け足しながらかけるのが面白い！！！
2次元配列以上になると、Numpyの本領が発揮される！かも！
次回は、以下の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 - 星座探し
Part1/22
おわり！