AtCoder Beginner Contest 166参加記(Python)

コンテスト参加記 AtCoder Python ABC166

AtCoder Beginner Contest 166(ABC166)に参加しました
atcoder.jp

目次



A問題：A - A - A?C(100点)

問題文
atcoder.jp

場合分けをすれば大丈夫です

pythonでの実装例

s = input()

if s == "ABC":
    print("ARC")
else:
    print("ABC")



B問題：Trick or Treat(200点)

問題文
atcoder.jp

お菓子を持っている人を数えていき、全体の人数から持っている人数を引いてあげます
被りがあったときに保存しないようにする時にはpythonの場合setが使えます

pythonでの実装例

n,k = map(int,input().split())
children = set()

for i in range(k):
    d = int(stdin.readline().rstrip())
    a = list(map(int,stdin.readline().rstrip().split()))
    for j in a:
        children.add(j)
 
print(n-len(children))



C問題： Peaks(300点)

問題文
atcoder.jp

他のつながっている標高と比較した際に、自分の標高が一番高いかどうかを判定します

最高地点であった場合１の値を持つリストを作り、各道ごとにもし自身の方が低かった場合に値を０に直します
答えはリストの合計値です

pythonでの実装例

n,m = map(int,input().split())
h = list(map(int,input().split()))
li = [[]for _ in range(n)]

# 自分が最高点だった場合１違ったら０
higest = [1]*n

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    li[a].append(b)
    li[b].append(a)
    if h[a] <= h[b]:
        higest[a] = 0
    if h[b] <= h[a]:
        higest[b] = 0

print(sum(higest))



D問題：I hate Factorization(400点)

問題文
atcoder.jp

与えられている数字が5乗されているところに注目します
詳しい照明は公式のpdfに載っていますが、aとbの範囲はそれほど大きくはならないことが分かります
(本番中は適当に-500から+500までで回しました)

範囲内でｘに合致する組があった場合それを出力します

ちなみにａ⁵－ｂ⁵の素因数分解をすると
ａ⁵－ｂ⁵＝(ａ－ｂ)(ａ⁴＋ａ³ｂ＋ａ²ｂ²＋ａｂ³＋ｂ⁴)
です

pythonでの実装例

x = int(input())

for i in range(-200,200):
    for j in range(-200,200):
        if i**5-j**5 == x:
            print(i,j)
            exit()



E問題：This Message Will Self-Destruct in 5s(500点)(※本番中未解答問題)

問題文
atcoder.jp

任意の2人を選び2人の番号の絶対値と身長の和が等しかった場合が何個あるかをカウントします
問題文にも書いてありますが普通に全列挙していると計算量が10**10程度になってしまい間に合いません

そこで以下のような変形を行います(i < j)

A_{j} - A_{i} = j+i
　　　　↓
i+A_{i} = j-A_{j}

まずi+A_{i}の値をN人分保存しておき、その後N人分j-A_{j}の値を見たときに等しいものがいくつあるかをカウントします
このような場合には辞書型を使うと効率的に検索を行うことができます

pythonでの実装例

n = int(input())
a = list(map(int,input().split()))

# i + A_iの値を保存する辞書
dic = {}
point = 0

for i,j in enumerate(a):
    if i+j in dic:
        dic[i+j] += 1
    else:
        dic[i+j] = 1

# j - A_jの値を辞書で検索をかける
for i,j in enumerate(a):
    if i-j in dic:
        point += dic[i-j]

print(point)



所感

今回の結果
atcoder.jp

ABCD問題の４完１ぺナで3798th / 11684でした（パフォーマンス:881　レート:974 → 965 (-9)）

前日に行われたABC165の結果はよかったのですが今回は微減。。。
C問題をグループ分けした個数を求める問題だと勘違いして手間取って時間を落としてしまいました

E問題は変形するという解法を思いつかなかったので、もっと経験を積む必要がありそうです

AtCoder Beginner Contest 160参加記(Python)

コンテスト参加記 AtCoder Python ABC160 heapq

AtCoder Beginner Contest 160(ABC160)に参加しました
atcoder.jp

目次



所感

f:id:algo_archit:20200329144445p:plain
今回の結果
ABCE問題の４完１ぺナで2552位でした（パフォーマンス1073）

C問題の問題に思ったよりも苦戦してしまい、回答時点で20分以上経過＋１ぺナで4000位程度と出遅れてしまいました

D問題もダイクストラ法で解こうと思っていたのですが、計算量的にTLEするのは目に見えていたので提出できず

そこであきらめてE問題に移動すると、問題文自体は簡単そう。。
前処理を工夫することで、優先度付きキューを使うことが出来そうだったので粘った結果ACできました

今までのコンテストでも感じてきましたがコンテスト中の負荷が膨大になっているのか、ジャッジが詰まっていたようです


公式のツイッターでもアナウンスがありましたが、同一APIでのコンテスト参加に制限がかけられるそうです
（大学のPCとかからアクセスしてる人が注意すればいい感じですかね？）


A問題：A - Coffee(100点)

問題文
atcoder.jp

coffeeという文字列と同じように、与えられた文字列が
「3番目と4番目の文字が等しく、5番目の文字と6番目の文字が等しい」か
を確認する問題です

pythonでの実装例

s = input()

if s[2] == s[3] and s[4] == s[5]:
    print("Yes")
else:
    print("No")



B問題：Golden Coins(200点)

問題文
atcoder.jp

与えられたコインをできる限り500円玉に交換し、さらに余ったコインを５円玉に交換しようという問題です

pythonではAをBで割ったときの商をA//B,余りをA%Bで求めることができます

500円玉＞５円玉の順に交換を行えばOKです
その際にコインの総数を減らすのを忘れないようにしましょう

pythonでの実装例

n = int(input())

total = 0

total += (n//500)*1000#500円玉に交換する

n %= 500#合計枚数を減らす

total += (n//5)*5#5円玉に交換する

print(total)



C問題：Traveling Salesman around Lake(300点)

問題文
atcoder.jp

池の周囲に設定された家をどのように廻れば最短経路になるか、といった問題です

時計回りか、反時計回りに回るかは開始地点と終了地点とを入れ替えるだけなので問題を解くうえでは関係ないです
そこで時計回り固定で考えることにします

それぞれの家間の距離が最大になっている区間を把握し、池一周分の距離から最大区間の距離を引いたものが答えです

与えられるリストに、池の基準点をまたぐときの場合を考慮して

「リストの１番目の要素＋池の１周の距離」をN＋１番目の仮想の家として追加します（下の図参照）
f:id:algo_archit:20200329162238j:plain

pythonでの実装例

k,n = map(int,input().split())
a = list(map(int,input().split()))

a += [a[0]+k]#aに要素を追加する

max_len = 0

for i in range(1,n+1):
    max_len = max(max_len,a[i]-a[i-1])

print(k-max_len)



D問題：Line++(400点)（本番中未解答問題）

問題文
atcoder.jp

問題文自体は難解なように見えますが、
「XとYの橋を使うか、使わないかで最短の距離を求める」
という風に言い換えることができます

N個の地点から２点を選択する _N C _2 = \frac{N(N-1)}{2}通りのパターンを探索し

・XYの橋を経由した場合
・XYの橋を経由しない場合

の２パターンを試し、最小値をその２点間の距離として格納します
(橋との距離には絶対値を取ります)

pythonでの実装例

n,x,y = map(int,input().split())

# 0スタートに合わせる
x -= 1
y -= 1

# 距離を格納するためのリスト
lengh_list = [0]*n

for i in range(n-1):
    for j in range(i+1,n):
        len_itoj = min(j-i,abs(x-i)+1+abs(y-j))
        lengh_list[len_itoj] += 1

for length in lengh_list[1:]:
    print(length)



E問題：Red and Green Apples(500点)

問題文
atcoder.jp

元からあった赤色のリンゴと緑色のリンゴに無色のリンゴを適時変色させることで、
全体のおいしさの価値を最大化しようという問題です

ここで、無色のリンゴを変色させるときには

「赤色と緑色のうち最も価値の低いリンゴと無色のうち最も価値の高いリンゴを交換できるだけ交換する」

という方法が価値を最大にするといえます

方針はわかってもこうしたリストにいちいちmin()関数を使って最低値を求めていたら計算時間が間にあいません
こうしたときに使えるのがheapq(優先度付きキュー)です

import heapq

li = [1,5,6,2,4]

heapq.heapify(li)# heapとして扱う

print(heapq.heappop(li))#1
print(heapq.heappop(li))#2
print(heapq.heappop(li))#4
print(heapq.heappop(li))#5
print(heapq.heappop(li))#6

heapq.heapify(list)の形でリストの先頭が常にリストの中の最低値を保持し続けます

heapq.heappush(追加したい要素)でリストに加え
heapq.heappop()で先頭の要素を排除します

heapqを使うと計算量を抑えながら問題を解くことができます

pythonでの実装例

import heapq

x,y,a,b,c = map(int,input().split())

p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

#価値が小さいように並べる
p.sort()
q.sort()

#価値が大きいように並べる
r.sort(reverse = True)

#結局赤色上位x個,緑色上位y個だけ残せばよい
p = p[a-x:]
q = q[b-y:]

# heapqの形にする
heapq.heapify(p)
heapq.heapify(q)

#交換できる限り交換を行う
for i in r:
    if p[0] <= q[0]:
        if i > p[0]:
            heapq.heappop(p)
            heapq.heappush(p,i)
    else:
        if i > q[0]:
            heapq.heappop(q)
            heapq.heappush(q,i)

print(sum(p)+sum(q))

#追記：
よくよく考えたらリストをあらかじめソートしているのでheapq使う必要ないのでは。。。

AtCoder Beginner Contest 159 (Python)

コンテスト参加記 AtCoder Python ABC159 競プロ精進

AtCoder Beginner Contest 159 (ABC159)をPythonで解きました
atcoder.jp

目次



所感

今回は用事があったためリアルタイムの参加はできず。。。

バーチャルコンテストで後日解いてみたところABCD４完の２WAで29:52でした
(実際のコンテストとは単純に比較できないですがパフォ1100くらい？)

今回はA問題とD問題に少しつながりがあったくらいでそれぞれの問題の毛色は異なる印象

C問題なんかは何となく答えはわかるけど、証明まで頭に浮かんで解くことはできませんでした


A問題：The Number of Even Pairs(100点)

問題文
atcoder.jp

N個の奇数が書かれたボールとM個の偶数が書かれたボールから２個を選んだ時にそれが偶数である場合は何通りか、という問題です

偶数＋偶数 = 偶数
奇数+奇数 = 奇数

ということさえ分かっていれば、あとはそれらの組み合わせを考えればOKです

ｎ個のものから順番を気にせず２つ選ぶ組み合わせは
_n C _2 = \frac{n(n-1)}{2}通りあります

Pythonでは以下のように実装できます

result = n*(n-1)//2

もしくはmath関数のfactorialを用いて

from math import factorial

#組み合わせを求める
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

result = combinations_count(n,2)

※factorial(x)でxの階乗x!を求められる

といった書き方ができますが今回は前者の方がすっきりとした書き方になります

pythonでの実装例

N,M = map(int,input().split())

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



B問題：String Palindrome(200点)

問題文
atcoder.jp

奇数の文字列が与えられて、全体として回文になっているのと同時に、真ん中の文字列を除く左側の文字列と、右側の文字列もそれぞれ回文になっているかを判定する問題です

文字列が回文になっているかを判定するためには、元の文字列を反転した際に反転した文字列と元の文字列とが一致しているかを確認できればよいです

Pythonでは元の文字列をSとした際にs[ : : -1]で文字列を反転させることが可能です

#元の文字列
s = "ATCODER"

#反転した文字列
s_mirror = s[::-1]

print(s_mirror)#REDOCTA

pythonでの実装例

s = input()

#全体として回文になっているか
if s != s[::-1]:
    print("No")
    exit()

mae = s[:len(s)//2]#前半部分
ushiro = s[(len(s)+1)//2:]#後半部分

#前部分が回文になっているか
if mae != mae[::-1]:
    print("No")
    exit()

#後ろ部分が回文になっているか
if ushiro != ushiro[::-1]:
    print("No")
    exit()

print("Yes")



C問題：Maximum Volume(300点)

問題文
atcoder.jp

縦、横、高さの合計がLであるときに体積を最大化する問題です

これはなんとなく３方向の長さがすべて等しければ体積は最大になるであろうということはわかります
証明は相加相乗平均の不等式を考えるとできるそうです

mathtrain.jp

(コンテスト中にあ！これ、相加相乗平均の不等式だ！などと考えられるつよつよ競プロerになりたい)

縦、横、高さをそれぞれa,b,cと置いたときに
( a \cdot b \cdot c )^ \frac{1}{3} ≦ \frac{a+b+c}{3}となり
両辺を３乗すると
a \cdot b \cdot c ≦ (\frac{a+b+c}{3})^3
つまり
a \cdot b \cdot c ≦ (\frac{L}{3})^3となります

これで不等式が成り立つa = b = cのとき体積が最大になることが示せました

pythonでの実装例

L = int(input())

print((L/3)**3)



D問題：Banned K(400点)

問題文
atcoder.jp

番号が書かれたボールのリストAが与えられ、i番目の要素A_iを除いたときに、残りのn-1個の要素から書かれている整数が等しいような異なる 2つのボールを選び出す方法の数を求める問題です

2つの要素の選び方はA問題のときと同じですね

要素の個数が最大200000個ほどになるため、書き方を間違えるとTLEしてしまいます

こういった場合あらかじめ各要素別に組み合わせを求めておき、参照できるようなリストを作っておくと計算量を減らすことができます

まずどの要素が何個あるのかを格納し、i番目の要素A_iを除くという条件を無視した際の全体の組み合わせを求めます

N = int(input())
A = list(map(int,input().split()))

#各要素が何個あるか
num_list = [0]*(N+1)
for i in A:
    num_list[i] += 1

#全体の組み合わせ
total = 0
for j in num_list:
    total += j*(j-1)//2

求める答えはこの全体の組み合わせから
A_i番目の要素ｎ個から２つ選ぶ _n C _2 = \frac{n(n-1)}{2}通りを引き、
A_i番目の要素から１つ除いたｎ－１個から２つ選ぶ _{n-1} C _2 = \frac{(n-1) \cdot (n-1)}{2}通りを足した数になります

これは _{n-1} C _2 - _n C _2 = 1-nとなるため
全体の組み合わせに1-nを足せばよいです

pythonでの実装例

N = int(input())
A = list(map(int,input().split()))

#各要素が何個あるか
num_list = [0]*(N+1)
for i in A:
    num_list[i] += 1

#全体の組み合わせ
total = 0
for j in num_list:
    total += j*(j-1)//2

for k in A:
    print(total+1-num_list[k])

ABC125 : C - GCD on Blackboard(Python)

競プロ精進 ABC125 AtCoder Python 最大公約数

ABC125: C - GCD on Blackboardをpythonで解きました

問題文

atcoder.jp
リストのうち１個を書き換えることにより全体の最大公約数を最大化しようという問題です

Atcoder Plobremsによると難易度は1217でABCのC問題にしては水色と高難易度
私がずっと放置してきた問題の１つです


解法

gcdとはgreatest common divisorの略で最大公約数を表します

最大公約数には結合法則が成り立ちます

例えばli = [12,18,9]というようなリストが存在していた場合に、
gcd(gcd(12,18),9)を求めるのと
gcd(12,gcd(18,9))を求めるのとでは
答えであるgcd(li) = 3には変わりがありません

どこから計算をしていっても最終的な答えは変わらないんですね

また、 A_i番目の数字を置き換える時には、他のn-1個の要素の最大公約数に変換するのが最適であることはすぐにわかります

なので A_i番目の数字を置き換える→i番目以外の要素の最大公約数を求める
という風に言い換えることができます

あとは全てのA_iにおいて
左側からi-1番目までの最大公約数を記録するL(i)と
i番目から右端までの最大公約数を記録するR(i)
において漸化式を作ります

漸化式は以下のようになります(※gcd(0,n) = nとする)
L(0) = 0\\ L(i + 1) = gcd(L(i), A(i))\\ R(N + 1) = 0\\ R(i) = gcd(R(i + 1), A(i))

i番目の要素を置き換えたと仮定したときの答えをM(i)とすると
M(i) = L(i) + R(i-1)の中の最大値が答えです

pythonにはmath関数にgcdが存在しますが、Atcoderのpythonは3.4系でmath.gcdに対してエラーを起こします
(もう少しすればAtcoderに3.8系が実装されるのでmath.gcdが使えるようになります)

そこで代替としてfractions関数のgcdを用います
fractions.gcd(a,b)でaとbの最大公約数が求められます

pythonでの実装例

※実装例では上記の漸化式を簡易的にしてあります

from fractions import gcd
 
N = int(input())
A = list(map(int,input().split()))
 
M = [0]*N
 
#漸化式を作る
L = [0]*N
R = [0]*N
 
for i in range(1,N):
    L[i] = gcd(L[i-1],A[i-1])
    R[N-1-i] = gcd(R[N-i],A[N-i])
 
for j in range(N):
    M[j] = gcd(L[j],R[j])
 
print(max(M))

パナソニックプログラミングコンテスト2020参加記(Python)

コンテスト参加記 パナソニックプログラミングコンテスト2020 AtCoder Python

ABC級企業コンのパナソニックプログラミングコンテスト2020に参加しました
atcoder.jp

目次

所感

f:id:algo_archit:20200315005051p:plain
今回の結果
60:45でABCの３完でした

なんとかレートを維持することに成功・・！

企業コンテストなので参加人数少なめなのかと思ってたら6600人もいてびっくりしました
最近は参加者ほんと多くて嬉しいです

今回は問題自体は簡単なものの、つまづきポイントが多めの印象でした

私もB問題で１WA、C問題で５WAしてしまいました。。
(こういったところで早解き出来る人は考察力高そう）

D問題は解けてるけどC問題は解けていない人も結構いたかもです


A問題：Kth Term(100点)

問題文
atcoder.jp

長さ32の数列の中からｋ番目の数字を取り出して出力する問題です
与えられた数列をリストに入れてあげさえすればそこまで難しくはないと思います

pythonでの実装例

li = [1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51]
k = int(input())
print(li[k-1])



B問題：Bishop(200点)

問題文
atcoder.jp

高さH、幅WのH*Wのマス目を持つ将棋盤に「角将」を置いて無限回移動した場合に何マスたどり着くことができるか？という問題です
(問題のタイトル見て知ったのですがチェスのビショップって角と同じ動きをするんですね)

最初見たときはめんどくさそう。。という感じだったのですが、サンプルを見るとマス目が偶数個だったら２で割った数、マス目が奇数個だったら２で割って切り上げた数が答えになりそうだという見当がつきました

そこで実装したのが以下のコード(WA)

H,W = map(int,input().split())
print((H*W+1)//2)

※h*wに1を足してあげてから2で割ることで小数点繰り上げ扱い
※もしくはmath関数のceil(float型の割り算を切り上げてint型で返す)を使って
print(math.ceil(H*W/2))
という書き方もできます

しかしこれを提出したところWA

何がおかしいのかコーナーケースを考えると、HかWのどちらかが１の場合そもそもその場から動けないということが判明

そこで場合分けを加えて書き換えた結果ACできました

pythonでの実装例

H,W = map(int,input().split())
if H == 1 or W == 1:
    print(1)
else:
    print((H*W+1)//2)



C問題：Sqrt Inequality(300点)

問題文
atcoder.jp

今回多くのWAを生み出した問題です
問題文自体はB問題のより簡単に見えますがfloat型の罠というか落とし穴を感じました。。
\sqrt{a}+ \sqrt{b} < \sqrt{c}
であることが証明できればいいのですが、これが思ったよりも大変

先ほども出てきたmath関数にはルートの計算ができるsqrtがあり、
まず提出したのがこのコード(WA)

from math import sqrt
a,b,c = map(int,input().split())
if sqrt(a)+sqrt(b) < sqrt(c):
    print('Yes')
else:
    print('No')

あえなく撃沈、コンテスト中は原因わからず

実はpythonのfloatは64であり
(a, b, c) = (249999999, 250000000, 999999998)
といった膨大な数で浮動小数点の計算を行うと下の方の桁で数値のずれが生じてしまうようです

そこで以下のような変換を行うことで整数の計算として問題を解きました
\sqrt{a}+ \sqrt{b} < \sqrt{c}
↓両辺を二乗する
a+ 2\sqrt{a \cdot b} + b < c
↓
2\sqrt{a \cdot b} < c-(a+b)
この時右辺が0以下であった場合不等号に矛盾が生じるのでNo
↓そうでない場合さらに両辺を二乗する
4ab < (c-(a+b))^2
これで整数の形で問題文を修正することができました

pythonでの実装例

a,b,c = map(int,input().split())
if c-(a+b) > 0 and 4*a*b < (c-(a+b))**2:
    print('Yes')
else:
    print('No')

ところでnumpyにはfloat128が存在します


D問題：Kth Term(100点)(本番中未解答問題)

問題文
atcoder.jp

（追記2020/04/22：ようやくこの問題が解けたので取り急ぎコードだけ載せます）

pythonでの実装例

import string

alphabet = string.ascii_lowercase

n = int(input())

def DFS(before,keta):
    num = 0
    if keta == n:
        print(before)
        return
    for i in before:
        num = max(num,alphabet.index(i))
    num += 1
    for j in range(num+1):
        DFS(before+alphabet[j],keta+1)

DFS("a",1)