目指せ水色コーダー!!!!!!
ということで、
レッドコーダーが教える、競プロ・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】
動的計画法:ナップザック 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)
いやー難しかった!
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
おわり!