この記事に記載した問題の一覧

AGC057 A Shik and Stone
ABC070 C Multiple Clocks
ABC123 C Five Transportations
AGC008 A Simple Calculator
ARC059 C いっしょ
ABC047 C 一次元リバーシ
ABC143 D Triangles
ABC035 B ドローン
AGC011 A Airport Bus
AGC002 B Box and Ball
ABC078 C HSI
ARC054 A 動く歩道
ABC065 C Reconciled?
パナソニックプログラミングコンテスト2020 C Sqrt Inequality

上記問題を解く上で学んだこと

reduceについて

reduceとは畳み込みのこと
高階関数の一種
- 高階関数とは、関数を引数にとる関数のこと(下は高階関数の例)
  1. map(各イテレータに関数を実行してイテレータで返す)
  2. filter（各イテレータに関数を実行した結果がTrueのもののみをイテレータで返す）)
reduce(function, iterater, initializer(option))の形で使用
functionをイテレータに順に実行していって結果を返す

桁の丸めについて

競プロではたまに桁の丸めによって、コードとしては正しく見えるが、WAになるケースがある(上の5.や14.)
四捨五入
round()を使うとダメなケースがあるので、(<num>*2+1)//2を使う。
ルート
math.sqrt()を使うとダメなケースがあるので、<num>**(decimal("0.5"))を使う。
※1:from Decimal import decimalが必要。
※2:decimalの引数は文字列で与える（数値で与えるとその時点で丸め誤差が生じる）。

二分探索について

ソート済みリストから値をサーチするときは、線形探索より二分探索をした方がいい（ことが多い）
<idx> = bisect.bisect_left(<list>, <value>)のような形で使うことができる。
※import bisectが必要

二分探索を用いることで線形探索と比較して、計算量を$O(n)$から$O(\log n)$に減らすことができる。

各問題の解法

AGC057 A Shik and Stone

所要時間：10分弱
ポイント：初めはcollections.counterを使おうと思ったが、#の数を数えるだけであれば、<list>のcount()で十分な気がしたのでそちらに変更して実装

# AGC057 A Shik and Stone

h,w = map(int, input().split())

_list = []
for i in range(h):
    _list += list(input())

if _list.count("#") == (h+w-1):
    print("Possible")
else:
    print("Impossible")

ABC070 C Multiple Clocks

所要時間：11分
ポイント：LCMを求める問題であることはぱっと見わかったので、LCMの実装方法をググった。
reduceについて勉強する時間は所要時間には含めない。

# ABC070 C Multiple Clocks

from functools import reduce
from fractions import gcd #python3.5より前
# from math import gcd      #python3,5以降

def lcm_base(x,y):
    return (x*y)//gcd(x,y)

def multi_lcm(numbers):
    return reduce(lcm_base, numbers)

n = int(input())
t_list = [int(input()) for i in range(n)]

print(multi_lcm(t_list))

ABC123 C Five Transportations

所要時間：-分
ポイント：紙に例を書いてみるとわかる

# ABC123 C Five Transportations
import math

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

_min = min([a,b,c,d,e])
_ans = math.ceil(n/_min)

print(_ans+4)

AGC008 A Simple Calculator

感想

パッと見簡単だが、パターン分けが意外と多い（もっときれいにできるかもしれない）
どちらかが0のときのパターン分けを雑にやったために2回WAになった。

# AGC008 A Simple Calculator

x, y = map(int, input().split())
_x = abs(x)
_y = abs(y)

if x > 0 and y > 0:
    if x <= y:
        print(y-x)
    else:
        print(x-y+2)
elif x * y < 0:
    print(abs(_y-_x)+1)
elif x == 0:
    if y >= 0:
        print(y)
    else:
        print(_y+1)
elif y == 0:
    if x > 0:
        print(x+1)
    else:
        print(_x)
else:
    if _x < _y:
        print(_y-_x+2)
    else:
        print(_x-_y)

ARC059 C いっしょ

感想

問題自体は簡単。計算量も全要素一つずつ計算しても問題なさそうだったのでそこも問題ない。
round()では四捨五入が正しくできないケースがあるので、(<num>*2+1//2)で四捨五入をした。（なぜround()が正しく四捨五入されないかはここでは割愛）

# ARC059 C いっしょ

n = int(input())
a_list = [int(x) for x in input().split()]

ave = ((sum(a_list) / len(a_list)) * 2 + 1) // 2

ans = sum([(x-ave)**2 for x in a_list])

print(int(ans))

ABC047 C 一次元リバーシ

感想

itertools.groupby()が思いつけば一瞬。
ただし、イテレータの要素数を取得する方法はないらしいので、↓のプログラムみたいにイテレータを使い切る必要がある

# ABC047 C 一次元リバーシ

import itertools

s = itertools.groupby(list(input()))

ans = 0
for _ in s:
    ans += 1

print(ans - 1)

ABC143 D Triangles

その1
- 安直に全探索で解いてみたが、案の定TLEになった。
その2
- 二分探索(bisect)を用いる。

その2を用いることで、計算量を$O(n^{3})$から$O(n^{2}\log n)$に減らすことができる。

その1

# ABC143 D Triangles TLE

n = int(input())
l_list = [int(x) for x in input().split()]

l_list.sort()
ans = 0

# (i < j < k) -> (_a < _b < _c)
for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = _a + _b
        for k in range(j+1,n):
            _c = l_list[k]
            if _c < _tmp:
                ans += 1
            else:
                break

print(ans)

その2

# ABC143 D Triangles

import bisect

n = int(input())
l_list = [int(x) for x in input().split()]

l_list.sort()
ans = 0

for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = bisect.bisect_left(l_list, _a+_b)
        if j < _tmp:
            ans += _tmp - j - 1

print(ans)

ABC035 B ドローン

Counter()を使えばすぐに解ける。

# ABC035 B ドローン
from collections import Counter

s = Counter(input())
t = int(input())

l = s["L"]
r = s["R"]
u = s["U"]
d = s["D"]
q = s["?"]

x = r-l
y = u-d

if t == 1:
    print(abs(x) + abs(y) + q)
else:
    _tmp = abs(x) + abs(y)
    if _tmp >= q:
        print(_tmp - q)
    elif (_tmp - q) % 2 == 0:
        print("0")
    else:
        print("1")

AGC011 A Airport Bus

その1
- はじめはbisect()(二分探索)さえ使えば間に合うと思ったが、TLEになった。
その2
- リストの頭からデータを取得する処理が多いので、dequeにしてみたところ通った。

リストの頭からデータを取得する場合、キューにすべきということを再確認した。

その1

# AGC011 A Airport Bus TLE
import bisect

n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]

t_list.sort()
ans = 0

while len(t_list) > 0:
    _tmp = t_list[0] + k
    _idx = bisect.bisect_right(t_list, _tmp)
    if c <= _idx + 1:
        t_list = t_list[c:]
    else:
        t_list = t_list[_idx:]
    ans += 1

print(ans)

その2

# AGC011 A Airport Bus
import bisect
from collections import deque

n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]

t_list.sort()
t_list = deque(t_list)
ans = 0

while len(t_list) > 0:
    _tmp = t_list.popleft() + k
    _idx = bisect.bisect_right(t_list, _tmp)
    if c-1 <= _idx:
        for _ in range(c-1):
            t_list.popleft()
    else:
        for _ in range(_idx-1):
            t_list.popleft()
    ans += 1

print(ans)

AGC002 B Box and Ball

# AGC002 B Box and Ball

n, m = map(int, input().split())

b_list = [0] * (n+1)
b_list[1] = 1
c_list = [1] * (n+1)

for i in range(m):
    _x, _y = map(int, input().split())
    c_list[_x] -= 1
    c_list[_y] += 1 
    if b_list[_x] == 1:
        b_list[_y] = 1
        if c_list[_x] == 0:
            b_list[_x] = 0

print(sum(b_list))

ABC078 C HSI

# ABC078 C HSI

n, m = map(int, input().split())

i = (1/2)**m

x = (100*(n-m) + 1900*m) / i
print(int(x))

ARC054 A 動く歩道

# ARC054 A 動く歩道

l, x, y, s, d = map(int, input().split())

ans = float("Inf")
j = (d-s)%l
r = (s-d)%l
ans = min(ans,j/(y+x))
if y > x:
    ans = min(ans,r/(y-x))
print(ans)

ABC065 C Reconciled?

# ABC065 C Reconciled?

import math

n, m = map(int, input().split())
A = 10**9 + 7

if abs(n-m) > 1:
    print("0")
elif n == m:
    print(((math.factorial(m)**2)*2)%A)
else:
    print((math.factorial(m)*math.factorial(n))%A)

パナソニックプログラミングコンテスト2020 C Sqrt Inequality

その1
math.sqrt()を使うと桁が丸められてNGになるケースがある。
その2
decimal.Decimal()を使うことで正しく計算ができる。

その1

# パナソニックプログラミングコンテスト2020 C Sqrt Inequality WA
import math
from decimal import Decimal

a, b, c = map(Decimal, input().split())
_a, _b, _c = map(math.sqrt, [a,b,c])

if _a + _b < _c:
    print("Yes")
else:
    print("No")

その2

# パナソニックプログラミングコンテスト2020 C Sqrt Inequality
from decimal import Decimal

a, b, c = map(int,input().split())
a, b, c = Decimal(a),Decimal(b),Decimal(c)
if a**Decimal("0.5") + b**Decimal("0.5") < c**Decimal("0.5"): 
    print('Yes')
else:
    print('No')