文系初心者が競技プログラミングをやってみた話～AtCoder Beginner Contest 139編～

前回、AtCoderなどを楽しんでいると書きました。

AtCoderというのは、競技プログラミングのサイトです。

atcoder.jp

競技プログラミングというのは、プログラミングを使って、パズルのような問題を早く、正確に解く競技だと考えて良いかと思います。

将棋で言えば、詰将棋でしょうか。

問題に対して、解法（どうすれば解けるか）を思いつく発想力と、

それを正確に速く効率的なプログラムに落とし込む実装力が問われてなかなかおもしろいです。

私は、むかーし、Pythonという言語を、Couseraのコースで習っただけのド素人ですが、たまに開催される大会に参加して楽しんでいる、というわけです。

この日曜日にもコンテストがあって参加してみました。

問題はこちらから御覧ください。

Tasks - AtCoder Beginner Contest 139

どんな感じで解いていったのか、メモ代わりに残してみます。

A問題：

S = str(input())

T = str(input())

cnt = 0

for i in range(3):

if S[i] == T[i]:

cnt = cnt +1　#cnt += 1

print(cnt)

2つの文字列を比較してマッチする分の個数をチェックする問題でした。

思いついたとおりに書いてみましたが、forの部分は、zip()などを使って簡潔に書けたかもしれません。

B問題：

A, B = map(int, input().split())

cnt = 0

num = 1

while num < B:

cnt = cnt + 1 #cnt += 1

num = num + A - 1 #num += A -1

print(cnt)

電源タップの必要な個数を考える問題。

実際タコ足は避けたほうが良いのでしょうが。ループを使って書いてしまいましたが、

本当は割り算のほうがすっきりするのでしょう。

C問題：

普段はこのへんから難しくなってくる気がするのですが、今回は割とすんなり行きました。

N = int(input())

H = [int(i) for i in input().split()]

mx = 0

tmp = 0

#print(H)

for i in range(N-1):

if H[i] >= H[i+1]:

tmp = tmp + 1

if tmp > mx:

mx = tmp

else:

tmp = 0

print(mx)

階段を下っていく問題。

下れるところまで下っていって、最大値をmxに記録していく、という単純な方法でも間に合いました。

D問題：

Cまで行けばいいかと、Dの前に風呂に入りましたが、Dも行けました。

数列のModの最大値を求める問題。

N = int(input())

print(N*(N-1)//2)

といっても余り褒められたものではなく。

（1、2、3・・・N）とあったときに、一つずらせば最大値だろうな、というのは、直感的にはわかったのですが、最初は、並べ替えた数列Pを作って、更に、最後尾を除いてsum()みたいなことをやってしまっていたのです・・・

そうすると計算時間がかかってしまって、タイムオーバー（TLE)。

単に等差数列の和なので、そのまま示してやればよかったですね。

E問題：

リーグの対戦順が可能か考える問題。

ループを回して、先頭からpop(リストから削除)してけばできるのかな～とか思ってたのですが、気力が起きずに撤退。popは先頭から削除するのは、めっちゃ遅いらしいとか、リストを裏っ返せばええんや、とか紆余曲折を経て、最終的には以下の形で通りました（後日）。

import copy

import collections

N = int(input())

A=

#結局dequeというやつを使うことにした。両端からの削除が早いらしい

for j in range(N):

A.append(collections.deque(int(i) for i in input().split()))

day = 0

empty = [0] * N

#一日目は全員を見て、次の日は前日に状況が変わった人だけみることに

s = [i for i in range(N)]

#whileループ一回を一日と考える

while N==N:

q =

day +=1

for i in s:

#i行目が空なら空であることを示すemptyリストを1に

if len(A[i]) == 0:

empty[i] = None

#iが既にqに入っていればパス

elif i in q:

pass

#i行目の末尾の数字で示された相手方が一致していればキューに追加

elif int(A[int(A[i][0])-1][0]) == i+1:

q.append(i)

q.append(int(A[i][0])-1)

s = copy.copy(q)

#ループ後にqが空ならそれ以上進めないので判定

if len(q) == 0:

if not(0 in empty):

print(day-1)

exit()

else:

print(-1)

exit()

#そうでなければキューに追加されている行の末尾を削除する

else:

for d in q:

A[d].popleft()

これでもpythonではなくpypyというやつでぎりぎりでした（pypyのが若干早いらしい。）。

本来的には、グラフ？の最長経路問題として解けるらしいのですが、いまいち枝とか経路とかの書き方のイメージが掴めていません。勉強しなきゃですね。

F問題：

ベクトルの合成の問題なんだろうなーと眺めていましたが、角度でソートする方法を考えてる間に、エネルギー切れに。

あとの部分は、普通に書けばいいだけだったので、粘ればよかったかもしれない。

import math

N = int(input())

A = []

for j in range(N):

A.append([int(i) for i in input().split()])

#arctanでY、Xから角度を求める。

for engine in A:

engine.append(math.degrees(math.atan2(engine[1], engine[0])))

if len(A)==1:

print(math.sqrt(A[0][0]**2 + A[0][1]**2))

exit()

#角度順にソートして、２周分のリストに。

A.sort(key=lambda x: x[2])

A = A + A

mx = 0

for i in range(N):

X = A[i][0]

Y = A[i][1]

temp = 0

for j in range(i+1, i+N):

if (math.sqrt(X**2 + Y**2)) > mx:

mx = math.sqrt(X**2 + Y**2)

X = X + A[j][0]

Y = Y + A[j][1]

if temp> math.sqrt(X**2 + Y**2):

break

temp = (math.sqrt(X**2 + Y**2))

if (math.sqrt(X**2 + Y**2)) > mx:

mx = math.sqrt(X**2 + Y**2)

print(mx)