千代田線を端から端まで歩いてみた

GWやることないから北綾瀬→代々木上原の千代田線ウォーキングチャレンジする pic.twitter.com/bsS4VdscAs

— u++ (@upura0) April 28, 2019

暇だったので、普段通勤などで使っている千代田線を歩いてみることにしました。下記シリーズの第3弾です。

upura.hatenablog.com

upura.hatenablog.com

なお事前の調査では、全長は21kmくらいとのことでした。

北綾瀬（11:37）

出発は北綾瀬駅。のどかでよい場所でした。

綾瀬（12:01）

北千住（12:50）

人類は荒川を渡るのに大きな迂回が必要なため、大幅に時間をロスしました。

町屋（13:43）

川や住宅街で迷ってしまい、ここでも時間を費やしました。

西日暮里（14:02）

ここからは駅間も短くなり、非常に順調でした。

千駄木（14:13）

根津（14:26）

湯島（14:42）

新御茶ノ水（15:00）

大手町（15:15）

二重橋前（15:33）

日比谷（15:35）

霞ケ関（15:51）

国会議事堂前（16:04）

赤坂（16:24）

日枝神社にも行きました。

乃木坂（16:36）

表参道（16:58）

明治神宮前（17:13）

代々木公園（17:31）

代々木上原（17:52）

最後に登り坂があって、少しつらかったです。

おわりに

序盤の荒川付近の影響でiOSの地図アプリの予測からは30分遅れてしまいましたが、合計5時間半で歩き切ることができました。

昨日の歩数。あんまりペース落ちてない。 pic.twitter.com/vqpWebE3wA

— u++ (@upura0) April 29, 2019

こういう取り組みは3回目ということもあり、当日も翌日も特に筋肉痛などありませんでした。また気が向いたらやります。

AtCoder Beginner Contest 125をPythonで解く

atcoder.jp

A - Biscuit Generator（100点）

• Tまでに何回ビスケットが生産されるか考える
• 0.5は無視で良い

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

ans = T//A * B
print(ans)

B - Resale（200点）

• それぞれの宝石の「価値-コスト」を考え、正の宝石の値を合計する

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

diff = [v-c if (v-c > 0) else 0 for v, c in zip(V, C)]
print(sum(diff))

C - Unification（300点）

• 問題文の条件は、どれか一つを削除した場合と同値
• 全通りを試して、最大値が答え
• 普通にやるとTLEするので、累積和ならぬ累積gcdして計算量を落とす

参考

Cの解法です pic.twitter.com/isCis7Kjk7

— アルメリア (@armeria_betrue) April 27, 2019

import fractions


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

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
    gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

参考（愚直な列挙＝TLE）

import fractions
from functools import reduce
import itertools


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

ans = []
for a in list(itertools.combinations(A, N-1)):
    ans.append(reduce(fractions.gcd, a))
print(max(ans))

D - Flipping Signs（400点）

• 操作を繰り返すと、初期のマイナスの数が偶数の場合は最終的にマイナスを0個に、奇数の場合は1個にできる
• 奇数の場合にマイナスを付けるのは絶対値が最も小さい値

マイナスの数が1個以下になる理由については、下記で図を用いて説明されています。

drken1215.hatenablog.com

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

num_of_minus = sum([a < 0 for a in A])
abs_A = [abs(a) for a in A]
ans = sum(abs_A)

if num_of_minus % 2 == 0:
    print(ans)
else:
    print(ans - 2 * min(abs_A))

Tenka1 Programmer Beginner Contest 2019をPythonで解く

atcoder.jp

A - On the Way（100点）

• 必ずしもA < Bではないことに注意して条件分岐

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

if (A[0] < A[2] < A[1]) or (A[1] < A[2] < A[0]):
    print("Yes")
else:
    print("No")

B - *e**** ********e* *e****e* ****e**（200点）

• 問題文の通りに実装

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

ans = ""

for s in S:
    if s == S[K-1]:
        ans += s
    else:
        ans += '*'

print(ans)

C - Stones（300点）

問題文の条件は、左端から連続するいくつかの石を白に、それ以外の石を黒にするという条件

editorial.pdf

• 全ての境目の値を試す
• とある境目を決めたとき「変えるべき個数」=「境目より左にある黒い石の個数」+「右にある白い石の個数」
• 累積和で持っておくと計算量が落とせる

from itertools import accumulate


N = int(input())
S = input()

black = [0]*N
white = [0]*N

for i, s in enumerate(S):
    if s == '#':
        black[i] = 1
    else:
        white[i] = 1

# 累積和
black = [0] + black
black = list(accumulate(black))
white = [0] + white[::-1]
white = list(accumulate(white))[::-1]

ans = []
for i in range(N+1):
    ans.append(black[i] + white[i])

print(min(ans))

D - Three Colors（600点）

• dpっぽいことは分かったが・・・
• 愚直解を書き上げるのも大事だと思ったので、TLEするコードを書いた
• 解説動画を見て勉強する

import itertools


N = int(input())
A = [int(input()) for i in range(N)]
cnt = 0

idx = [i for i in range(3)]
idx_l = [idx for _ in range(N)]
ans = list(itertools.product(*idx_l))
for a in ans:
    first = 0
    second = 0
    third = 0
    if (len(set(a)) == 3):
        for i, v in enumerate(a):
            if v == 0:
                first += A[i]
            elif v == 1:
                second += A[i]
            else:
                third += A[i]
        path = [first, second, third]
        if 2 * max(path) < sum(path):
            cnt += 1
print(cnt)

Data Driven Developer Meetup 【番外編 好きな論文について語る会】 #1 の発表資料

これは何？

↓のイベントで話す際の資料です。

d3m.connpass.com

自己紹介

• 事業会社のデータアナリスト＆エンジニア
• Data Driven Developer Meetupは #4 で登壇
• ブログやGitHubで読んだ論文をまとめています

Many analysts, one dataset: Making transparent how variations in analytical choices affect results

29組のデータアナリストに同じデータセットと同じ質問を与えても、分析結果がバラバラだったという研究

upura.hatenablog.com

時間があったら皆大好き🍣の話も

upura.hatenablog.com

AtCoder Beginner Contest 124をPythonで解く

予定があったので、リアルタイムでは参加できませんでした。

atcoder.jp

A - Buttons（100点）

• AとBを1回ずつ取る場合は、A==Bのときのみ
• それ以外は同じのを連続で取る

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

if (A == B):
    print(A + B)
else:
    print(max(A, B) * 2 - 1)

B - Great Ocean View（200点）

• それぞれの山に対して、自分よりも海に近い山の集合での最大値を考える（最大値が自分自身であれば海が見える）

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

cnt = 0
for i in range(len(H)):
    if (max(H[0:i+1]) == H[i]):
        cnt += 1

print(cnt)

C - Coloring Colorfully（300点）

• 「0101010....」か「1010101....」に揃えることになる
• どちらに揃えるのが良いか比較する

S = input()
N = len(S)
even = S[0::2]
odd = S[1::2]
ptn0 = N - (even.count('0') + odd.count('1'))
ptn1 = N - (even.count('1') + odd.count('0'))
print(min(ptn0, ptn1))

D - Handstand（400点）

• 以前に解いたABC032C「列」で書いた「尺取り法」のコードを流用した
• 尺取り法はこの記事などで勉強していた
• 具体的な処理はコード内のコメント参照

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

S = S + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

# 立った人の連続の数
if (S[0] == '0'):
    stand = 1
else:
    stand = 0

L = 0
R = 0

# 尺取り法
while (R < N):
    # 右端を進めることが可能（立った人の連続の数がK以下）なら、右端を進める
    if (stand <= K):
        # 立った人の連続の数が増えるなら1足す
        if (S[R] == '1' and S[R + 1] == '0'):
            stand += 1
        # 答えの更新
        ans = max(ans, R - L + 1)
        R += 1
    # 進められない場合、左端と右端が同じなら両者を進める
    # 左端が右端を追い越さないための処理
    elif (L == R):
        L += 1
        R += 1
    # それ以外は左端のみを進める
    else:
        # 立った人の連続の数が減るなら1減らす
        if (S[L] == '0' and S[L + 1] == '1'):
            stand -= 1
        L += 1
        # 左端のみを進めた場合は答えを更新し得ない

print(ans)

Kaggle PetFinderコンペで準優勝しました

KaggleのPetFinderコンペで準優勝しました。

Solutionの概要はdiscussionで公開しています。
PetFinder.my Adoption Prediction | Kaggle

AtCoder Beginner Contest 123をPythonで解く

「AtCoder Beginner Contest 123」を解きました（リアルタイムでは参加できませんでした）。

atcoder.jp

A - Five Antennas（100点）

• 一番大きい座標と小さい座標の差がKより大きいかで条件分岐
• 最初問題文のa~eの不等号を見落としていたので無駄にmax, minを取ってしまった

A = [int(input()) for i in range(5)]
K = int(input())

if (A[-1]-A[0] <= K):
    print("Yay!")
else:
    print(":(")

B - Five Dishes（200点）

• 10の位まで繰り上げる
• 1の位が1~9のうちで1に近いほど、最後の料理に採用されやすい

A = [int(input()) for i in range(5)]
B = [a - a % 10 + 10 if a % 10 != 0 else a for a in A]
diff = [(b - a) for a, b in zip(A, B)]

print(sum(B)-max(diff))

C - Five Transportations（300点）

• 結局のところ、一番輸送量が小さい経路で詰まる
• 一番輸送量が小さい経路を一番最初に通過すると考えると分かりやすい

import math


N = int(input())
A = [int(input()) for i in range(5)]
print(math.ceil(N/min(A))+4)

D - Cake 123（400点）

• Kが高々3000以下なので、A, Bの直積を考えた後に上位3000だけ残し、Cとの直積を考える
• 降順sort部分を "AB = sorted(AB)[::-1]" にするとTLEした

import itertools


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse=True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])