2020-06-14

AtCoder 東京海上日動プログラミングコンテスト2020

AtCoder

AB2完の緑パフォでした。そして今回のコンテストでようやくレート緑になることができました！ f:id:spider-man-dance:20200614005522p:plain

個人的にレート緑は最初の目標として掲げていたので、ようやくですが入緑できてほっとしています。これからも少しずつ伸ばしていきたい。

A - Nickname

問題のリンク

概要

省略

コード

S = input()
print(S[:3])

B - Tag

問題のリンク

概要

二次元軸での鬼ごっこ問題。鬼役の座標と速度。逃げる役の座標と速度が与えれるので、制限時間以内に追いつけるかどうかを判定。

制約

省略

考察

省略

コード

A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

diff = abs(A-B)

if (V-W)*T >= diff:
    print('YES')
else:
    print('NO')

C - Lamps

問題のリンク

概要

省略

制約

$1 ≤ N ≤ 2 × 10^{5}$
$1 ≤ K ≤ 2 × 10^{5}$
$0 ≤ A_i ≤ N$

考察

　今回解けなかった問題。解説で学んだいもす法を振り返りながら実装して行こうと思います。

いもす法の考え

f:id:spider-man-dance:20200614121614p:plain

　スライドにしてみましたが、これが一番分かりやすいと思います。左図はのように一定の区間をドンドン足し合わせていく操作については、右図のようにその始点と終点+1のポイントに着目することで、大幅に計算量を減らせます。（始点と終点の間全てに+1をしてしまっては計算量が膨大になってしまうことはイメージできると思います。）よってこの方法を使うと、スライドの操作自体は見ての通り、 $Order(N)$ になるので、これを $K$ 回だけ繰り返すとすると、 $Order(NK)$ で問題を解くことが可能です。　ただここで問題が一つあり、最悪ケースの場合（ $N = 2 × 10^{5}, K = 2 × 10^{5}$ ）で $Order(NK)$ だとAtCoderでは通りません。ただこれも解説で触れていたのですが、今回の問題設定の場合、 $lon(N)$ の操作で収束してしまうことが分かるので、 $K$ はが $41$ 回以上の場合、問答無用で答えは[N] * Nの配列になってしまいます。

コード

import numpy as np
from numba import jit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)

# 高速化
@jit
def imo(a, n):
    imos = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        imos[max(0, i-a[i])] += 1
        imos[min(n, i+a[i])+1] -= 1

    # 累積和はnumpyの方が高速
    immo = np.zeros(n+1, dtype=np.int64)
    immo = np.cumsum(imos)

    return immo[:n]


for _ in range(min(K, 41)):
    A = imo(A, N)

print(*A)

2020-06-07

第三回アルゴリズム実技検定

AtCoder 資格試験

　A ~ O の全15問中、Gまで7問完答で初級でした。普段のAtCoderと違って実務よりの問題が多いとは聞いてましたが、確かに現実にありそうなシーンを意識して作問してる雰囲気は感じました。今回のAtCoder アルゴリズム実技検定はコロナウイルス影響で無料受験可能だったので、これを機に初めて受けてみたのですが、やはりもっと基本的なとこから鍛えていかなければならないなと改めて実感。

G問題までの解法

　自分の解法。もっと効率的な方法はあると思う。

種類	概要
A	`str.lower()` メソッドで
B	与えられたクエリを一つ一つ実直に
C	そのまま`for文`。ただし $R=1$ の時はすぐ`A`を出力。じゃないと $R=1$ の時に無限ループになる。
D	めちゃくちゃ大変。`if文`の列挙。解答例は割と上手くやっていた（それでもややこしい）
E	無効グラフの問題。制約的にそのまま実直にクエリを実行
F	最初問題文の意味が分からずかなり時間取られる。上手い方法が思いつかず`que`を使って実直に実装
G	幅優先探索

H - ハードル走

問題のリンク

概要

3つの行動から一つ選んで実行できる。（詳細は問題リンクから）
$0$ からスタートして、 $L$ までいく時の最短時間を求める。
ただし間に $N$ 個のハードルがある。

制約

$2 ≤ L ≤ 10^{5}$
$1 ≤ N ≤ L$
$0 \lt x_1 \lt x_2 \lt \cdots \lt x_N \lt L$
$2 ≤ T_1, T_2, T_3 ≤ 1000$
$T_1, T_2, T_3$ は偶数

考察

　問題の感じからDP。もしくは貪欲法あたりだろうなと考えてました。どうやらDPで行くらしいです。考えた方は以下の通り。

dp[0, inf, inf, inf, ... ]で初期化。
min(dp[i+1], dp[i]+行動1でかかる時間)で更新。もし座標 $i$ にハードルがあった場合T3を後者に追加
min(dp[i+2], dp[i]+行動2でかかる時間)で更新。もし座標 $i$ にハードルがあった場合T3を後者に追加
min(dp[i+4], dp[i]+行動3でかかる時間)で更新。もし座標 $i$ にハードルがあった場合T3を後者に追加

　基本は上記の様にして動的計画法( $Order(N)$ )してく感じ。ただゴール近くに差し迫った場合、ジャンプ中に飛び越している可能性もあるので、最後に微調整が必要。

コード

N, L = map(int, input().split())
X = [False] * (L+10)
hard = list(map(int, input().split()))

for x in hard:
    X[x] = True

T1, T2, T3 = map(int, input().split())

dp = [float('inf')]*(L+10)
dp[0] = 0

for i in range(L+1):
    cost = T3 if X[i] else 0
    dp[i+1] = min(dp[i+1], dp[i] + T1 + cost)
    dp[i+2] = min(dp[i+2], dp[i] + T1 + T2 + cost)
    dp[i+4] = min(dp[i+4], dp[i] + T1 + T2*3 + cost)
    if i+1 == L:
        dp[i+1] = min(dp[i+1], dp[i] + T1//2 + T2//2 + cost)
    elif i+2 == L:
        dp[i+2] = min(dp[i+2], dp[i] + T1//2 + 3*T2//2 + cost)
    elif i+3 == L:
        dp[i+3] = min(dp[i+3], dp[i] + T1//2 + 5*T2//2 + cost)
 
print(dp[L])

I - 行列操作

問題のリンク

考察

　普通に実装すると時間計算量以前に空間計算量的にもヤバくてメモリエラー起こしてました。解法みた所、実はそれに近い形で頭の中では解き方をイメージしてたものの、実装ミスで解けなかった感じです。

コード

N = int(input())
rows = [i for i in range(N)]
columns = [i for i in range(N)]
transposed = False

Q = int(input())
for _ in range(Q):
    q = list(map(int,input().split()))

    if q[0] == 3:
        transposed = not transposed
    else:
        A, B = q[1]-1, q[2]-1
        if q[0] == 1:
            if transposed:
                columns[A], columns[B] = columns[B], columns[A]
            else:
                rows[A], rows[B] = rows[B], rows[A]
        elif q[0] == 2:
            if transposed:
                rows[A], rows[B] = rows[B], rows[A]
            else:
                columns[A], columns[B] = columns[B], columns[A]
        elif q[0] == 4:
            if transposed:
                A, B = B, A
            r,c = rows[A], columns[B]

            print(N*r+c)

2020-06-01

PyTorch Scheduler Class の Chaining

PyTorch

今回はPyTorch 1.4.0から追加された新機能であるSchedulerのChainingについてです。この方のQiita記事で知ったのですが、PyTorchのschedulerに新機能が追加された様です。

qiita.com

内容はシンプルで、今までは学習ループの中に1種類しか組み込めなかったschedulerを複数重ねて使えると言うことです。具体例をみていきましょう。

import torch
from torch.optim.lr_scheduler import ExponentialLR, CosineAnnealingLR
from torch.optim import SGD
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()

lr_cos, lr_exp, lr = [], [], []

# 初期化
model = [torch.nn.Parameter(torch.randn(2, 2, requires_grad=True))]
optimizer = SGD(model, 1e-2)
optimizer.zero_grad()
scheduler_cos = CosineAnnealingLR(optimizer, T_max=20, eta_min=1e-6)
for epoch in range(200):
    optimizer.step()
    optimizer.zero_grad()
    scheduler_cos.step()
    lr_cos.append(scheduler_cos.get_last_lr()[0])

# 初期化
model = [torch.nn.Parameter(torch.randn(2, 2, requires_grad=True))]
optimizer = SGD(model, 1e-2)
optimizer.zero_grad()
scheduler_exp = ExponentialLR(optimizer, gamma=0.97)
for epoch in range(200):
    optimizer.step()
    optimizer.zero_grad()
    scheduler_exp.step()
    lr_exp.append(scheduler_exp.get_last_lr()[0])

# 初期化
model = [torch.nn.Parameter(torch.randn(2, 2, requires_grad=True))]
optimizer = SGD(model, 1e-2)
optimizer.zero_grad()
scheduler_cos = CosineAnnealingLR(optimizer, T_max=20, eta_min=1e-6)
scheduler_exp = ExponentialLR(optimizer, gamma=0.97)
for epoch in range(200):
    optimizer.step()
    optimizer.zero_grad()
    scheduler_exp.step()
    scheduler_cos.step()
    lr.append(optimizer.param_groups[0]['lr'])

plt.plot(lr_cos, label='CosineAnnealing', linestyle='dashed')
plt.plot(lr_exp, label='Exponential', linestyle='dashed')
plt.plot(lr, label='Fusion', color='red', linewidth=3)
plt.legend(bbox_to_anchor=(0, -0.1), loc='upper left', borderaxespad=0)
plt.show()

f:id:spider-man-dance:20200601140933p:plain

この様な形でCosineAnnealingとExponentialを使って新たなタイプのschedulerを作れていることが分かります。この機能と以下の方のコードを使えば、今まで自分でクラスを作っていたWarmup系のschedulerも簡単に作れそうです。

github.com

!pip install git+https://github.com/ildoonet/pytorch-gradual-warmup-lr.git
from warmup_scheduler import GradualWarmupScheduler

lr = []

# 初期化
model = [torch.nn.Parameter(torch.randn(2, 2, requires_grad=True))]
optimizer = SGD(model, 1e-2)
optimizer.zero_grad()
scheduler_cos = CosineAnnealingLR(optimizer, T_max=400, eta_min=1e-6)
scheduler_wup = GradualWarmupScheduler(optimizer, multiplier=1, total_epoch=20, after_scheduler=scheduler_cos)
for epoch in range(200):
    optimizer.step()
    optimizer.zero_grad()
    scheduler_cos.step()
    scheduler_wup.step()
    lr.append(optimizer.param_groups[0]['lr'])

plt.plot(lr, label='Warmup Cosine Annealing', color='red', linewidth=3)
plt.legend(bbox_to_anchor=(0, -0.1), loc='upper left', borderaxespad=0)
plt.show()

f:id:spider-man-dance:20200601141656p:plain

2020-05-31

AtCoder ABC 169

AtCoder

ABCD4完の緑パフォでした。今までのABC挑戦の中で、最速でDまで解けたけど（18分）、Cでつまづいてしまいました。考え方については途中気付いたけどなぜか通らずゴニョゴニョしてたら通った感じです。こういったプログラミング言語あるある（桁溢れ問題）は意識していきたい（特に小数扱う際）

A - Multiplication 1

問題のリンク

概要

$A×B$ を求める。

制約

$1 ≤ A, B ≤ 100$

考察

自分が見てきた中でAtCoder史上、最も簡単な問題でした。

コード

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

B - Multiplication 2

問題のリンク

概要

$N$ 個の整数の積を求める。結果が $10^{18}$ を超える場合は、代わりに-1を出力

制約

[tex: 2 ≤ N ≤ 10⁵]
$0 ≤ A_i ≤ 10^{18}$
入力は全て整数

考察

愚直に実装。0があるかどうかだけ最初に判定してないと、実際の答えは0なのに誤って-1を出力してしまうので注意

コード

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

if min(A)==0:
    print(0)
    exit()

ans = 1
for a in A:
    ans *= a
    if ans>10**18:
        print(-1)
        exit()

print(ans)

C - Multiplication 3

問題のリンク

概要

$A×B$ を求める。 $B$ は小数第2位まで与えられる。

制約

Aは整数
Bは小数第2位まで与えられる
$0 ≤ A ≤ 10^{15}$
$0 ≤ B ≤ 10$

考察

　A問題の小数問題ということで、桁溢れエラーを誘ってる感がぷんぷん漂ってはきていたのですが、結局実装でミスりまくりました。（計7回）　とりあえずなるべく小数問題を避けたいので、文字列やら整数やらで代用できる様にゴニョゴニョしてたらいつの間にか解けたって感じですが、次からはこういうの気をつけたい。

コード

from math import floor

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

B1 = int(B[:-3])
B2 = int(str(B)[-2:])

ans1 = A * B1
ans2 = A * B2 // 100

ans = ans1 + ans2
print(floor(ans))

D - Div Game

問題のリンク

概要

はじめに整数 $N$ が与えられる。 $N$ に対して、以下の操作を何度できるか。

- ある素数[tex: p]と正の整数[tex: e]を用いて、[tex: z = p^e]と表せる。
- [tex: N]が[tex: z]で割り切れる。
- 以前の操作で選んだどの整数とも異なる。
- [tex: N]を[tex: N/z]に置き換える。

制約

入力は全て整数
$1 ≤ N ≤ 10^{12}$

考察

まず、 $N$ を素因数分解
次にそれぞれの素因数から問題文の条件を満たす $z$ がどれだけ作れるかをループでカウント

コード

N = int(input())

def factorization(n):
    arr, temp = [], n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

fac = factorization(N)
ans = 0

for k, v in fac:
    cnt = 1
    if k != 1:
        while True:
            v -= cnt
            if v < 0:
                break
            ans += 1
            cnt += 1

print(ans)

2020-05-18

AtCoder ABC 168

AtCoder

ABC3完の茶色パフォでした。今回のレベルでDまで行けなかったのは不甲斐ないので、改めて精進したい。

A - ∴ (Therefore)

問題のリンク

概要

$N$ の一の位で場合分け

制約

$N$ は $999$ 以下の正の整数

考察

特になし

コード

N = input()

if int(N[-1]) in [2,4,5,7,9]:
    print('hon')
elif int(N[-1]) in [0,1,6,8]:
    print('pon')
else:
    print('bon')

B - ... (Triple Dots)

問題のリンク

概要

文字列 $S$ の長さで場合分け

制約

$K$ は $1$ 以上、 $100$ 以下の整数
$S$ は英小文字からなる文字列
$S$ の長さは $1$ 以上、 $100$ 以下

考察

特になし

コード

K = int(input())
S = input()

if len(S)<=K:
    print(S)
else:
    ans = S[:K] + '...'
    print(ans)

C - : (Colon)

問題のリンク

概要

ある時計の長針の長さ、短針の長さ、及び現時刻が与えられた時の長針の先端と短針の先端の距離

制約

入力は全て整数
$1 ≤ A, B ≤ 1000$
$0 ≤ H ≤ 11$
$0 ≤ M ≤ 59$

考察

　三平方の定理をググれば理論上はすぐに解ける問題。だが当初、短針の角度を(H/12) * 360)としてしまっており、計算が合わず時間をロスしてしまった。正しくはminuteも考慮した((H/12) * 360) + (30*(M/60))。これに気づくまでに時間がかかってしまった。今後は気を付けたい。

コード

import math

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

ka_a = ((H/12) * 360) + (30*(M/60))
ka_b = M/60 * 360

kakudo = max(ka_a, ka_b) - min(ka_a, ka_b)
kakudo = min(kakudo, (360-kakudo))
cos = math.cos(math.radians(kakudo))

if kakudo==180:
    print(A+B)
    exit()

ans = A**2 + B**2 - 2*A*B*cos

print(math.sqrt(ans))

D - .. (Double Dots)

問題のリンク

概要

いわゆる最短経路問題
最短経路を通った際、次に進む先のノードの番号を求める

制約

入力は全て整数
$2 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 2×10^{5}$
$1 ≤ A_i, B_i ≤ N(1 ≤ i ≤ M)$
$A_i ≠ B_i(1 ≤ i ≤ M)$
どの $2$ 部屋間も、道路をいくつか通って行き来できる

考察

根( $1$ 番目の部屋)をスタートに幅優先探索をしていく
制約上、どの二部屋間も行き来できる（つまり必ず1のゴールにたどり着けるという保証がされている）ので、Noの答えはあり得ない。つまり、探索すべきグラフは必ず一つしかあり得ない。

コード

from collections import deque

def bfs_tree(graph, v=1):
    """
    graph: グラフ
    v: スタート
    """
    # 矢印がどこを向いているか
    # -1だと未探索
    arrow = [-1]*len(graph) 
    q = deque()
    q.append(v)
    arrow[v] = 0
    while q:
        now = q.popleft()
        for next_v in graph[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
pre = []

for _ in range(M):
    A, B = map(int, input().split())
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)

arrow = bfs_tree(graph, 0)

print('Yes')
for i in range(1, N):
    print(arrow[i]+1)

2020-05-10

AtCoder ABC 167

AtCoder

ABCD4完の緑パフォでした。

A - Registration

問題のリンク

概要

以下の二つの文字列が等しいか否か
$S$ , 及び $T$ の末尾を削ったもの

制約

$1 ≤ |S| ≤ 10$
$|T| = |S| + 1$

考察

特になし

コード

S = input()
T = input()

if S == T[:-1]:
    print('Yes')
else:
    print('No')

B - Easy Linear Programming

問題のリンク

概要

$1$ が書かれたカードが $A$ 枚、 $0$ が書かれたカードが $B$ 枚、 $−1$ が書かれたカードが $C$ 枚あります。これらのカードから、ちょうど $K$ 枚を選んで取るとき、取ったカードに書かれた数の和として、ありうる値の最大値はいくつか。

制約

入力は全て整数である。
$0 ≤ A, B, C$
$1 ≤ K ≤ A + B + C ≤ 2×10 ^{9}$

考察

特になし

コード

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

if K<=A:
    print(K)
elif A<K<=A+B:
    print(A)
elif A+B<K<=A+B+C:
    print(A-(K-A-B))

C - Skill Up

問題のリンク

概要

高橋くんは学びたいアルゴリズムが $M$ 個あり、スタート時点で $M$ 個全て理解度は $0$ である。
参考書が $N$ 冊ある。 $i$ 番目の参考書を読むとそれぞれのアルゴリズムの理解度が $A_{ij}$ 上がる。また $i$ 番目の参考書は $C_i$ 円である。
全ての理解度が $X$ 以上になるための最小コストを求めよ。

制約

入力は全て整数
$1 ≤ N, M ≤ 12$
$1 ≤ X ≤ 10 ^{5}$
$1 ≤ C_i ≤ 10 ^{5}$
$1 ≤ A_{ij} ≤ 10 ^{5}$

考察

　とりあえず全探索が間に合いそうなことは分かった。（解説でも全探索しか方法はないと言っていた。）そこで買う or 買わないのbit全探索を実装。ただ、少しコードが長くなって正解するまでに実装ミスを連発してしまった。尚、DFSで実装する方が効率的。

コード

import numpy as np

N, M, X = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(N)]

ans = 10**9

for i in range(1<<N):
    cost = 0
    tisiki = np.array([0]*M)
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1
    
    for k in range(N):
        if cond[k]==1:
            b = book[k]
            cost += b[0]
            tisiki += np.array(b[1:])
    
    if np.all(tisiki>=X):
        ans = min(ans, cost)

if ans < 10**9:
    print(ans)
else:
    print(-1)

D - Teleporter

問題のリンク

概要

$1$ ~ $N$ までランダムに番号のついた $N$ 個の街がある。
それぞれの街にはテレポーテーターが設置されており、それぞれの転送先は $A_i$ である。
$K$ 回移動した際に泊まっている街を求めよ。

制約

$2 ≤ N ≤ 2×10^{5}$
$1 ≤ A_i ≤ N$
$1 ≤ K ≤ 10 ^{18}$

考察

$K$ が物凄く大きいためそのまま $K$ 回for文を回すのは不可能。
一度ループが検出できれば、残っている移動回数から最終的なストップ地点を求めることが可能。
移動していく処理は再帰関数で実装。
他の人のコードを見てるとどうやら再帰関数を使わずwhile文を使って書いてる人もいた。

コード

import sys
sys.setrecursionlimit(10**9)

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

log = []
check = [False]*N

def func(x, iter):
    x = A[x-1]

    if iter+1 == K:
        return x
    if check[x-1]:
        ix = log.index(x)
        loop = log[ix:]
        tmp = (K-iter-1)%len(loop)
        return loop[tmp]
    else:
        log.append(x)
        check[x-1] = True
        iter += 1
        return func(x, iter)

print(func(1, 0))

2020-05-09

Random Grid Shuffle の実装

画像エンジニアリング

ある画像をいくつかのブロックに分割し、ランダムに並び替えたい時があったのでメモ。 albumentationsにもRandomGridShuffleクラスがあり、似たようなことはできるのですがこちらは各ブロックのフリップが出来なそうだったので自分で実装しました。もっと効率的に書けそうな気はするので改善の余地あり。

f:id:spider-man-dance:20200509011633p:plain