あるぱかのブログ

AtCoder茶(レート541)

CPythonとPyPyの比較

ABC341CでCPythonだとTLEする問題から処理系の特徴を把握すべきだろうと比較を行った記録

CPythonとPyPyの違い

こちらの記事がたぶん全てなので正直改めて検証する必要もないけどせっかくなのでやりました。

【AtCoder】Pythonで競プロをするときの注意点まとめ【競技プログラミング】 #Python - Qiita

雑にまとめるとモジュールのインポートや再帰関数を使う場合はCPythonのほうが良いらしい？

ので本記事では

・シンプルに計算量の多そうな問題

・再帰関数を使う問題

・外部モジュールを呼び出す問題（DFS）

で両処理系の比較をしてみます。

 

AtCoder Beginner Contest 338　C - Leftover Recipes

リンク：C - Leftover Recipes (atcoder.jp)

概要： N種類の材料から料理 Aと料理 Bを作ります。作れる最大数を出力してね

いずれかの料理の数を固定してもう一方を作れる最大数を探索を繰り返すシンプルながら試行回数が多くなるケースがある全探索問題です。

計算量は O(N) \times Q_{max}です。

CPythonで公式解説の通りやると一部ケースでTLEしました。

（探索の途中で不可能がわかったらbreakする処理したらギリ通せた）

#ABC338 C - Leftover Recipes
N=int(input())
Q=list(map(int, input().split()))
A=list(map(int, input().split()))
B=list(map(int, input().split()))

ans=0
for a in range(10**6+1):
    b=10**8
    for i in range(N):
        if Q[i]-A[i]*a<0:
            b=-10**8
        elif B[i]>0:
            b=min(b,(Q[i]-A[i]*a)//B[i])
    ans=max(ans,a+b)
print(ans)

結果

Cpython：AC \times12、TLE \times6

提出 #49744255 - AtCoder Beginner Contest 338

PyPy：AC（170ms）

提出 #50453575 - AtCoder Beginner Contest 338

想定通りPyPyのほうが格段に速くACできました。

 

AtCoder Beginner Contest 247 C - 1 2 1 3 1 2 1

リンク：C - 1 2 1 3 1 2 1 (atcoder.jp)

概要： S_{i-1} N S_{i-1}の文字列を出力してね

再帰を使った問題です。

メモ化が必要なので外部モジュールも使って自動メモ化を行っています。

#ABC247 C - 1 2 1 3 1 2 1
from functools import cache
@cache
def f(N):
    if N == 1:
        return [1]
    else:
        return f(N-1) + [N] + f(N-1)
n = int(input())
ans = f(n)
print(*ans, sep = ' ')  

結果

CPython：AC（26ms）

提出 #50268949 - AtCoder Beginner Contest 247

PyPy：AC（84ms）

提出 #50453784 - AtCoder Beginner Contest 247

確かにPyPyのほうが遅いです。

 

AtCoder Beginner Contest 293 C - Make Takahashi Happy

リンク：C - Make Takahashi Happy (atcoder.jp)

概要：互いに異なる整数の書かれたマスだけ踏んでゴールできる組み合わせ数を出力してね

外部モジュールdequeを使ったDFSです。

#ABC293 C - Make Takahashi Happy
from collections import deque
H, W = map(int, input().split())
A = []
for x in range(H):
    a = list(map(int, input().split()))
    A.append(a)
#print(A)

q = deque([[0, 0]])
pre = [-1]*(H+W-1)
count = 0

while q:
    cnt = q.popleft()
    x, y = cnt
    pre[x+y] = A[x][y]
    if x == H-1 and y == W-1:
        if len(pre) == len(set(pre)):
            count += 1
#            print(pre)
    else:
        nx = [x+1, y]
        ny = [x, y+1]
        if x+1 < H:
            q.appendleft(nx)
        if y+1 < W:
            q.appendleft(ny)

#    print(q)
#    print(pre)
print(count)  

結果

CPython：AC（117ms）

自分の提出 - AtCoder Beginner Contest 293

PyPy：AC（99ms）

提出 #50453875 - AtCoder Beginner Contest 293

計算量の多い問題ではモジュールインポートのデメリットより計算量のメリットが勝つこともあるようです。

結果

基本はPyPyで問題無いように思います。

再帰や外部モジュールを使ったコードでTLEするときは解法自体を見直したほうが良い場合が多そうです。

今まで特に考えずCPythonでやっていましたが今後はPyPyを主に使っていきます。

 

トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

 

A - Print 341

リンク：A - Print 341 (atcoder.jp)

概要： Nの数だけ 10を並べて最後に 1を付け足した文字列を出力してね

数字としてではなく文字列として扱ったほうが簡単です。

#ABC341 A - Print 341
N = int(input())
ans = ''
for i in range(N):
    ans += '10'
ans += '1'
print(ans)  

提出リンク：提出 #50329219 - トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

 

B - Foreign Exchange

リンク：B - Foreign Exchange (atcoder.jp)

概要： i国の通貨を A_i単位所有しています。 A_i通貨 S_iを消費して A_{i+1}通貨 T_iを得る操作を繰り返して最終的に A_N国通貨は何単位になるか出力してね

なんか問題文の意味がよくわからなくて10分くらい悩んだりWA叩いたりした。

無駄に毎ステップ最大値の比較しているところに迷走のあとが見て取れます。

題意の通り i=0から i=N-1まで順番に両替していって最後の N国通貨の数を出力すればいいです。

#ABC341 B - Foreign Exchange
N = int(input())
A = list(map(int, input().split()))
mx = A[-1]
for i in range(N-1):
    s, t = map(int, input().split())
    A[i+1] += (A[i] // s) * t
    A[i] = A[i] % s
    mx = max(A[-1], mx)
print(mx)

提出リンク：提出 #50358134 - トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

 

C - Takahashi Gets Lost 

リンク：C - Takahashi Gets Lost (atcoder.jp)

概要：二次元盤面で座標 (i, j)をスタート地点として Tの文字列の通り上下左右に移動します。この間一度も海に入らずに済む場所として考えられるスタート地点の数を出力してね

盤面サイズが H \leq 500、 W \leq 500、移動数が N \leq 500なので愚直に全探索しても 1.25 \times 10^{9}回の試行回数になります。

本問では制限時間が3秒与えられているので無駄なことをしなければ十分間に合いそうです。

・・・そのはずが本番中にACできませんでした。

本番提出コードが下記になります。

#ABC341 C - Takahashi Gets Lost
H, W, N = map(int, input().split())
T = input()
G = []
for i in range(H):
    G.append(input())
#print(G)

DX = [0] * len(T)
DY = [0] * len(T)

for i in range(len(T)):
    if T[i] == 'L':
        DY[i] = -1
    if T[i] == 'R':
        DY[i] = 1
    if T[i] == 'U':
        DX[i] = -1
    if T[i] == 'D':
        DX[i] = 1

count = 0
visited = '.'
target = '.'*len(T)
for i in range(H):
    for j in range(W):
        x, y = i, j
        if G[x][y] == '.':
            for dx, dy in zip(DX, DY):
                x += dx
                y += dy
                if G[x][y] == '#':
                    break
                else:
                    visited += G[x][y]
                    #print(visited)
                    if visited == target:
                        count += 1
        visited = '.'
print(count)  

提出リンク：提出 #50371863 - トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

結果：AC \times11、WA \times7、TLE \times22

WAの原因は visitedの初期値が空欄では無いため N-1回の移動ができればOKと判定してしまっている点です。

翌朝修正したものが次のコードです。

文字列の追加よりも移動マス数を flagとして足し上げるほうが管理しやすいと考えて変更入れています。

#ABC341 C - Takahashi Gets Lost
H, W, N = map(int, input().split())
T = input()
G = []
for i in range(H):
    G.append(input())
#print(G)

DX = [0] * len(T)
DY = [0] * len(T)

for i in range(len(T)):
    if T[i] == 'L':
        DY[i] = -1
    if T[i] == 'R':
        DY[i] = 1
    if T[i] == 'U':
        DX[i] = -1
    if T[i] == 'D':
        DX[i] = 1

count = 0
flag = 1
for i in range(1, H-1):
    for j in range(1, W-1):
        if G[i][j] == '.':
            x = i
            y = j
            flag = 0
            for dx, dy in zip(DX, DY):
                x += dx
                y += dy
                if G[x][y] == '#':
                    break
                else:
                    flag += 1
                    if flag == len(T):
                        count += 1
                        flag = 0
print(count)  

提出リンク：提出 #50403264 - トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

結果：AC \times18、TLE \times22

（なんか余計なflag = 1が残ってますね・・・今気づきました）

WAはACになりましたがTLEは解消されませんでした。

動き自体は変わってないので当然です。

これ以上の高速化が思いつかなかったので他の方々の提出を見てみましたが同じ処理で通してる人多いので何が問題か分からず・・・

ダメ元で処理系をCPythonからPyPyに変えた結果が以下リンクです。

提出リンク：提出 #50403247 - トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

結果：AC \times40、641ms

全く同じコードでもこんなに処理速度違うんですね。

勉強になりました。

 

結果

本番成績としてはA,Bの2完でした。

B問題で無駄に躓いたりWAしたりで悲しい結果になりました。

 

 

精進(2024/2/16)

 

AtCoder ProblemsのRecommendation(Moderate)を解く

AtCoder Beginner Contest 081 C - Not so Diverse

diff = 430

リンク：C - Not so Diverse (atcoder.jp)

概要： N個のボールに何種類かの数字が書かれています。 K種類以内にするために数字の書き換えが必要なボールの最小数を出力してね

度数分布作って少ない順に処理すれば良さそう。

Pythonでは度数分布を作る便利な関数があるので使いましょう。

Counterによって ｛1 : 3｝（1が3個）というように数字をキーとして配列が作られます。

今回は何の数字かは関係ないので数だけを取り出して適当に配列 Bとしています。

また少ない順に並べ替えて配列 Cとして、余分な数字の種類 Dのぶんを数え上げて答えとして出力しました。

 

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
num = Counter(A)
B = []
for key in num:
    B.append(num[key])
C = sorted(B)
D = len(B) - K
if D > 0:
    ans = sum(C[:D])
else:
    ans = 0
print(ans)  

提出リンク：提出 #50296999 - AtCoder Beginner Contest 081

 

AtCoder Beginner Contest 150 C - Count Order

diff = 422

リンク：C - Count Order (atcoder.jp)

概要： 1～ Nの数字を重複なく並べ替えた数列が2つあります。考えられる数列すべてを辞書順に並べた時の順位の差を出力してね

問題文にもある通り 1～ Nの順列は N!通りありますが制約が N \leq 8なので全探索しても間に合いそうです。

でも探索するたって元の順列どうやって全部つくろう・・・なんとか計算で辞書順ひねくりだせんかな・・・

 

いやわからん（解説）

 

ということで"permitations"という関数を使うといいそうです。

配列 numに入っているものを重複なく並べ替えて作った順列を辞書順にリストアップしてくれます。

permutationsはタプル形式で順列を保有しているので検索したい順列もタプルに型を合わせる必要があります。

順列を作るのに O(N!)(たぶん)、順列 Pと Qの位置を探すのにすれぞれ O(N)なので計算量としては O(N!)だと思います。


#ABC150 C - Count Order
from itertools import permutations
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

num = [i for i in range(1, N+1)]
a = list(permutations(num))

ans = abs(a.index(P) - a.index(Q))
print(ans)

提出リンク：提出 #50300842 - AtCoder Beginner Contest 150

 

AtCoder Beginner Contest 293 C - Make Takahashi Happy

diff = 432

リンク：C - Make Takahashi Happy (atcoder.jp)

概要：二次元盤面で互いに異なる数字のみを踏んでゴールにたどり着く組み合わせ数を出力してね

左上スタートで右か下のみに進んで右下を目指すということでとり得る経路は最短距離のみになります。

ゴールの可否や条件満たす経路のうち1つだけ出力する問題ならBFSで一瞬なんですが組み合わせの数ということは何とかして全ての組み合わせを試行してゴールできたものの数を数え上げる必要があります。

 

（1時間後）

 

DFSで経路記録したり上書きしたりすれば何とかなりそうだな！

ということでキューに座標を追加していき、取り出すタイミングで現在地の数字を経路配列 preに記録していきます。

現在地 (x, y)がスタートから何マス目かは x + yで計算しています。

今回は必ず最短経路でゴールにたどり着くため、スタートゴール含めて踏むマスの数 =preのサイズは (H-1) + (W-1) + 1になります。

現在地がゴールの座標 (H-1, W-1)の場合は経路に同じ数字が無いか判定を入れています。

 

#ABC293 C - Make Takahashi Happy
from collections import deque
H, W = map(int, input().split())
A = []
for x in range(H):
    a = list(map(int, input().split()))
    A.append(a)
#print(A)

q = deque([[0, 0]])
pre = [-1]*(H+W-1)
count = 0

while q:
    cnt = q.popleft()
    x, y = cnt
    pre[x+y] = A[x][y]
    if x == H-1 and y == W-1:
        if len(pre) == len(set(pre)):
            count += 1
#            print(pre)
    else:
        nx = [x+1, y]
        ny = [x, y+1]
        if x+1 < H:
            q.appendleft(nx)
        if y+1 < W:
            q.appendleft(ny)

#    print(q)
#    print(pre)
print(count)  

提出リンク：提出 #50300193 - AtCoder Beginner Contest 293

 

今回は1勝2敗ということで同じような難易度帯でも解ける解けないがまだ激しいですね・・・

 

精進(2024/2/12)

 

AtCoder ProblemsのRecommendation(Moderate)を解く

CODE FESTIVAL 2015 あさぷろ Easy B - ヘイホー君と置き換え

diff=430くらい

リンク：B - ヘイホー君と置き換え (atcoder.jp)

概要：文字列 Sを前半後半に分けて、前半＝後半にするために必要な操作数を出力してね

よくある文字列の置換操作の操作数を求める問題です。

今回は文字を自由に置き換えできるので簡単です。

（ n文字目と m文字目を入れ替えみたいな制約が無い）

まず Sの文字数が奇数の場合は前半後半に分割不可能なので -1を出力します。

偶数なら最悪全文字を置き換えれば題意は満足できます。

とりあえず Sの頭から \dfrac{N}{2}文字目までを前半として文字列 A、 \dfrac{N}{2}文字目から最後を後半として文字列 Bとしました。

スライス記法で S[:N//2]とすることで0 ~   \dfrac{N}{2} -1文字目までを取り出しています。

あとは 0から \dfrac{N}{2}まで走査して文字が異なる場所を数え上げれば答えになります。

実際に文字列を置換する必要はありません。

 

N = int(input())
S = input()
if N % 2 != 0:
    print(-1)
else:
    A = S[:N//2]
    B = S[N//2:]
    count = 0
    for i in range(N//2):
        if A[i] != B[i]:
            count += 1
    print(count)

提出リンク：提出 #50230109 - CODE FESTIVAL 2015 あさぷろ Easy (atcoder.jp)

 

CODE FESTIVAL 2017 qual C B - Similar Arrays

diff=430くらい

リンク：B - Similar Arrays (atcoder.jp)

概要：配列 Aの各要素 A_iに対して配列 Bの各要素 B_i = A_i -1  or  A_i or A_i +1としたときの配列 Bの全項の積が偶数になるパターン数を出力してね

配列長さ Nの制約が10以下なので最悪全探索しても 3^{10} = 59,049パターンなので間に合いそうです。

が、多重for文でややこしくなりそうなので別の方法を考えます。

今回は積が偶数か奇数かだけ分かればいいという点を使います。

かける数に1つでも偶数があれば積は偶数になります。

逆に言えばすべて奇数をかけるパターンでしか積が奇数になりません。

つまり全パターン 3^{N}から配列 Bの全要素が奇数のパターンの数を引くことで答えとなります。

またA_iが偶数なら B_i = A_i \pm1の範囲で奇数となりえるのは2通り( A_i +1, A_i -1)あり、A_iが奇数なら B_i = A_i \pm1の範囲で奇数となりえるのは1通り( A_i)あります。

配列 Aの各要素について偶奇判定を行うことで Bの全項が奇数になるパターン数を把握できます。

これにより計算量 O(N)で答えを求めることができます。

 

N = int(input())
A = list(map(int,input().split()))
count = 1
for i in A:
    if i % 2 == 0:
        count *= 2
    else:
        count *= 1
print(3**N - count)  

提出リンク：提出 #50230176 - CODE FESTIVAL 2017 qual C (atcoder.jp)

 

AtCoder Grand Contest 029 A - Irreversible operation

diff=430くらい

リンク：A - Irreversible operation (atcoder.jp)

概要： Bと Wからなる文字列について BWの並びを WBにする操作を可能な限りやって最大回数を出力してね

これもよくある文字列のスワップです。

この問題では文字列 Sの長さが最大 2 \times 10^{5}なので計算量 O(N)でないとTLEになります。

つまり文字列 Sを頭から走査して BWのスワップをする動作を愚直に繰り返す方法では計算量が最悪 O(N^{N})となるためACできません。

(例えば Bが 2 \times 10^{5} -1個並んだあとに Wがあるような並び)

ということで、題意の操作を繰り返すと最終的にどういう形になるか、それに対して初期値はどのくらい離れた状態にあるのかを考えることにします。

BWの並びを WBにするということは言い換えると Wを左側に、 Bを右側に固めることになります。

例として入力例2の BWBWBWは6回の操作で最終的に WWWBBBの並びになるはずです。

Wの位置に着目して、最初は 1, 3, 5番目にありますが最終的には 0, 1, 2番目に移動しています。

1つ目は 1 - 0 = 1の距離を、2つ目は 3 - 1 = 2の距離を、3つ目は 5 - 2 = 3の距離を移動していることがわかります。

移動距離の総和をとると6となりこれが答えとなります。

実際には複数ある Wを区別する必要はないので、各 Wの初期位置の総和と操作完了後の Wの位置の総和を引き算することで答えを出します。

ちなみに 0～ N-1の総和は \dfrac{N(N-1)}{2}で計算できます。

文字列 Sを1巡だけ走査すれば目的を果たせるので計算量は O(N)となり十分高速です。

 

S = input()
N = len(S)
count = 0
dist = 0
for i in range(N):
    if S[i] == 'W':
        count += 1
        dist += i
W = (count*(count-1))//2
print(abs(W-dist))  

提出リンク：提出 #50230261 - AtCoder Grand Contest 029

 

鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）

 

A - Arithmetic Progression

リンク：A - Arithmetic Progression (atcoder.jp)

概要：初項A、末項B、公差Dの等差数列を半角スペース区切りで出力してね

 

A問題らしいシンプルな文法を問う問題です。

pythonではrange(初項、末項+1、間隔)で簡単に記述できます。

提出リンク：提出 #50139788 - 鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）

#ABC340 A - Arithmetic Progression
A, B, D = map(int,input().split())
ans = [i for i in range(A, B+1,D)]
print(*ans, sep = ' ')  

 

B - Append

リンク：B - Append (atcoder.jp)

概要：リストに数字を追加したり指定した番号の数字を出力したりしてね

 

クエリという言葉でぎょっとするかもしれませんが単純なリスト操作ができれば問題無く解けます。

Q回与えられるクエリの1個目をflagの頭文字f、2個目をnumberの頭文字nとして記載しています。

fが1のときはリストAに数字nを後ろから追加、fが2のときはリストAの最後尾から数えてn番目を出力します。

pythonではリストの最後尾をA[-n]として取得できます。

あるいはA[len(A)-n]でも同じことができます。

提出リンク：提出 #50148194 - 鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）

Q = int(input())
A = []
for i in range(Q):
    f, n = map(int,input().split())
    if f == 1 :
        A.append(n)
    if f == 2:
        print(A[-n])  

 

C - Divide and Divide

リンク：C - Divide and Divide (atcoder.jp)

概要：数字Nを2で割って2つの整数（上界、下界）にします。操作を行うたびにN円を支払います。すべての数字が1になるまで行ったときの出費を計算してね

制約が  10^{17} なので計算量O(N)だとTLEになります。

よくわからんけど愚直に2で割ってコストをカウントして全部の数字が1になるまで繰り返せばええやろと書いたコードが下記になります。

 

from collections import deque
N = int(input())

q = deque([p])
count = 0
while q:
    cnt = q.popleft()
    count += cnt
    if cnt % 2 == 0:
        d = p = cnt//2
    else:
        d = cnt//2
        p = cnt//2 + 1
    if d >= 2:
        q.append(d)
    if p >= 2:
        q.append(p)
print(count)

 

テストケース実行して入出力例2まではあったので喜んでいたら入出力例3で一生計算が終わらなくて絶望しました。（この時点で制約について気づいていない）

同じ数字を何度も計算するのでメモ化すれば計算量落とせるな、一個前の数字で次に計算するべき数字が決まるから再帰が使えそうだな、まで頭が回りましたがメモ化も再帰も書いたことがなかったのでここで終了しました。

 

D - Super Takahashi Bros.

リンク：D - Super Takahashi Bros. (atcoder.jp)

概要：重み付きグラフで最短経路を出してね

ダイクストラ法するだけのボーナスタイムです。

ただ私がダイクストラ法書いたことなかったので残念ながら・・・

 

結果

ただのタイピング速度みたいなA,B問題を5分ちょいで書いただけのコンテストになりました。メモ化再帰やダイクストラ法を勉強するいい機会になり学びが多かったのでヨシ！とします。

 

はじめに

自己紹介

こんにちは、@pakaaaaaaaaaaと申します。

AtCoderでpythonを使っています。

2024/2/10時点でレート283の灰色です。

ここではABC参加中に考えていたことなど書き留めて参ります。

 

各種アカウント：pakaaaaaaaaaa | Twitter | Linktree