23
58

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】

Last updated at Posted at 2020-04-17

目指せ水色コーダー!!!!!!

ということで、
レッドコーダーが教える、競プロ・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文にしてみた!

test.py
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 追記)
今ならこんな感じでコード書く。

test.py
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こっちの方がスマートでした!!!

test.py
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()は小数点以下切り捨て!

test.py
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()こっちは使えます!!!
参考コードは一応残しておきます・・・

参考コード

test.py
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を上書きしていく!

test.py
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)をつけると、
インデックスがその数字からスタート!

test.py
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を使って、
部分文字列の全探索ができる!!!
すごい!!!

test.py
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問目を組み合わせたような問題。
でも、次からはすらすらとコードが書けるようになった気がする!

test.py
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次元配列を用意して・・・
行列を入れ替えて足し算・・・
その最大値!

test.py
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マスター(仮)になった!
ので、今ならこんな感じでコード書く。

test.py
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
おわり!

次(Part2/22)へ

23
58
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
23
58

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?