ABC206参戦記

今回もPanasonicさん協賛のABCです。過去の記事にも書いていますが、今までのPanasonicさん主催、協賛のコンテストは全てレートを落としているので、相性が悪いです。

この記事は、ABC206のAからC問題までを私が理解した内容で振り返ります。

私のレートは600手前、使用言語はPython3です。

A – Maxi-Buying

標準入出力と四則演算、条件分岐が書けるかを問われる問題。

受け取ったNに、*1.08 した値を整数にして場合分けすればOKですね。

整数にするのは、int() や、//1 を利用するのが良いと思います。math.floor() もありますが、私は今回はint()で提出しました。

import math

# N=155
print(N*1.08)               # => 167.4
print(int(N*1.08))          # => 167
print(N*1.08//1)            # => 167.0
print(math.floor(N*1.08))   # => 167

また、プログラミングで少数を扱うときは、誤差が生じるため、出来るだけ少数が出ないように、108をかけてから100で割るほうが良いようです。(今回の問題では、1.08をかけて小数部分を切り捨てても、誤差でWAになることはないです。)

# AtCoder Beginner Contest 206（Sponsored by Panasonic）
# A - Maxi-Buying

N=int(input())

n=int(N*1.08)
if n<206:
    print("Yay!")
elif n==206:
    print("so-so")
else:
    print(":(")

今回の問題は、出力する文字が、”Yes”や”No”というものではないので、注意が必要でした。問題のページからコピペするのが安全だと思います。

B – Savings

繰り返し処理が書けるかが問われる問題。

whileループでもforループ(途中でbreakする前提)でも書けますが、個人的にforループの方が好きなので、forループで書いていきます。

答え用の変数を用意して、足し算していきます。答え用の変数が、Nを超えたときの i(日にち) を出力してループを抜ければOKですね。

Nが制約の最大値である、10⁹の場合を考えても、繰り返し処理をする回数は、44721回 ( i を0から処理すると+1回 ) で終了します。

# AtCoder Beginner Contest 206（Sponsored by Panasonic）
# B - Savings

N=int(input())

ans=0

for i in range (1,10**9):
    ans+=i
    if ans>=N:
        print(i)
        exit()

このほかにも、貯金箱に入る金額は、自然数の和を求める数式を知っていれば i 日目にNよりも貯金箱に入っている金額は大きいかを判定していく、二分探索の問題として扱うことができます。

def is_ok(n):
    '''
    okの条件を記載する。
    個別の問題でそれぞれ定義する。
    '''    
    s=n*(n+1)//2
    if s>=N:
        return True
    else:
        return False

def megru_bisect(ok,ng):
    while(abs(ok-ng)>1):
        mid=(ok+ng)//2
        if is_ok(mid):
            ok=mid
        else:
            ng=mid
    return ok

N=int(input())

ok=10**18+5
ng=0

ans=megru_bisect(ok,ng)

print(ans)

C – Swappable

二重のfor文を回避する方法を考える問題。私は、setとdictを使用しました。

二重ループで全ての i , j の組を調べると、計算量が多くなって、TLEしてしまいます。この問題はAi と Aj が異なる値の組が知りたいということなので、すべての組から、同じ値になる個数を引けばよいことがわかります。
同じ値の個数は、今まで見てきた数をsetとdictで管理していきました。
数列を左から順に処理していき、

1. 今までに出てきたか。
2. 出てきたなら、何回出てきたかを調べる。
3. 出てきてなかったら、出てきた数に追加する。
4. 出てきた回数を1増やす。

を判定していきます。

# AtCoder Beginner Contest 206（Sponsored by Panasonic）
# C - Swappable

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

s=set()
dic=dict()

ans=0

for i in range (N):
    if A[i] in s:
        occ=dic[A[i]]
    else:
        s.add(A[i])
        occ=0
    ans+=i-occ
    occ+=1
    dic[A[i]]=occ

print(ans)

ちなみに、冒頭でも書いている通り、Panasonicさん主催/協賛のコンテストでレートが下がり続けていましたが、今回のコンテストでついにレートが上がりました！今回のコンテストはD問題まで解けたのが大きかったですね。