今日の精進(20191229)

昨日AGCが辛かったのではじめてCodeforcesのコンテストに参加した。英語も読めないし問題も解けないしで3完で終了Hackされたので2完でした。採点の仕組みが違うようで、Atcoderと違ってなかなかレートが反映されない。早く結果みたいが…。

Minutes Before the New Year

要は、今の時間は12/31のhh/mmなので、1/1の0:00まであと何分かを出力してくれという問題だった。英語読むの辛いね。

# coding: utf-8  
N = int(input())  
for i in range(N):  
    h, m = map(int, input().split())  
    ans = 0  
    ans += 60 - m  
    ans += 60 * (23 - h)  
    print(ans)  

Candies Division

n個の飴をk人の子供にできるだけ平等に配りたいという問題。このできるだけというのが

  • 多くもらう子と少なくもらう子の差は1以下。
  • 少なくもらう子の数は$\frac{k}{2}$までにすること。(これを読むのに時間がかかった。)

を満たしていなければならない。問題がわかればやるだけだった。

# coding: utf-8  
N = int(input())  
for i in range(N):  
    ans = 0  
    n, k = map(int, input().split())  
    ans += n // k * k  
    n -= n // k * k  
    ans += min(n, k//2)  
    print(ans)  

Friend and Gifts

N人の子供がそれぞれ他の子供にプレゼントを渡す問題。入力中の0は誰に渡すかわからない状態なので、これを適切に決めて出力する。
数字の被りがなくかつ自分にプレゼントを渡さないようにする。
やり方としては、0のインデックスを保存して、入力の0にプレゼント先に指定されていない子の
インデックスを入れるようにした。しかしインデックスを頭からやると自分に渡してしまうので、保存したインデックスの始点の真ん中からにした。あってるのかよくわかっていないが、とりあえずこれで通りはした。ちょっともにょる…。
 Hackされたので間違ってるっぽい。

# coding: utf-8  
N = int(input())  
A = list(map(int, input().split()))  
L = [False] * N  
l = []  
for i in range(N):  
    if A[i] != 0:  
        L[A[i]-1] = True  
    else:  
        l.append(i)  
idx = 0  
a_idx = len(l) // 2  
while idx < N:  
    if L[idx] == False:  
        A[l[a_idx]] = idx+1  
        if a_idx == len(l) - 1:  
            a_idx = 0  
        else:  
            a_idx += 1  
    idx += 1  
print(*A)  

Move and Win

AGCでdifficultyが灰だったので解いたがまじで簡単だった。2人の距離の差の偶奇で場合分け。偶数の場合はAlice、奇数の場合はBorysが勝つ。考察時間がとても短く済んだのは昨日のAGCのおかげ。

# coding: utf-8  
N, A, B = map(int, input().split())  
if (B - A) % 2 == 0:  
    print("Alice")  
else:  
    print("Borys")  

Wanna go back home

同じくAGCのdifficulty灰。東西と南北でそれぞれ0か1つでもあれば返ってこれる。ただし、東1、西0みたいな場合には返ってこれないので注意する。

# coding: utf-8  
S = input()  
l = {"E":0, "W":0, "S":0, "N":0}  
for i in range(len(S)):  
    l[S[i]] += 1  
f1, f2 = False, False  
if (l["W"] != 0 and l["E"] != 0) or l["W"] == l["E"] == 0:  
    f1 = True  
if (l["N"] != 0 and l["S"] != 0) or l["N"] == l["S"] == 0:  
    f2 = True  
print("Yes" if f1 and f2 else "No")  

浮気調査

どこかの家を経由したほうが早く着くことは無いので、それぞれの家の座標に対して初期位置からの距離+その家から現在地までの距離がT*V以下であれば、少なくとも1つの家には寄れることになるので、その場合YESを出力する。上の条件を1つも満たさなかった場合はNO

# coding: utf-8  
from math import ceil  
tax, tay, tbx, tby, T, V = map(int, input().split())  
N = int(input())  
flag = False  
for i in range(N):  
    x, y = map(int, input().split())  
    tmp_road = ((tax - x) ** 2 + (tay - y) ** 2) ** 0.5  
    tmp_road += ((x - tbx) ** 2 + (y - tby) ** 2) ** 0.5  
    if tmp_road <= T * V:  
        flag = True  
print("YES" if flag else "NO")  

音楽ゲーム

.のときはボタンを押さないことと。のときには長押しができないことに注意。

# coding: utf-8  
import numpy as np  
music = []  
N = int(input())  
for i in range(N):  
    tmp = list(input())  
    music.append(tmp[:])  
music = np.array(music)  
ans = 0  
# print(music)  
for i in range(9):  
    s = music[0][i]  
    if s != ".":  
        ans += 1  
    for j in range(1, N):  
        # print(j, i)  
        if s != music[j][i]:  
            s = music[j][i]  
            # print(j, i, s)  
            if s != ".":  
                ans += 1  
        elif s == "x":  
            ans += 1  
print(ans)  

Shink and Stone

スタート地点を決めたら、コマは次の動きを繰り返すことでしか条件を満たさない。

  1. その行でできるだけ右に動く
  2. 1段下に動く

これを繰り返して通った軌跡をTrueとして、その数が#の数と同じになればPossibleとした。

# coding: utf-8  
import numpy as np  
H, W = map(int, input().split())  
board = []  
tb = [[False] * W] * H  
tb = np.array(tb)  
cnt = 0  
for i in range(H):  
    tmp = list(input())  
    for j in range(W):  
        if tmp[j] == "#":  
            cnt += 1  
            if "s" not in globals():  
                s = [i, j]  
    board.append(tmp[:])  
board = np.array(board)  
tb[s[0], s[1]] = True  
for i in range(H):  
    for j in range(s[1], W):  
        if board[i][j] == "#":  
            s[1] = j  
            tb[s[0], s[1]] = True  
    if s[0] < H - 1:  
        s[0] += 1  
    if board[s[0], s[1]] == "#":  
        tb[s[0], s[1]] = True  
    else:  
        break  
print("Possible" if cnt == np.sum(tb) else "Impossible")  

Triangle

解説&他の人の見ながらAC。自分で解きたかった…
2つ決めて他の1つは条件を満たすように決めるので、最初はそのように2分探索をしていたのだが、PythonではTLE、PyPyではWAになってしまった(なぜ…)。
bisect_leftで先に決めた2つの和が挿入できる所を探索し、2つ目のインデックス~探索したところまでは3本目の候補となるのでそれらを足していく。計算量は$O(N^2\log{N})$となる。すごい賢い…

# coding: utf-8  
from bisect import bisect_left  
N = int(input())  
L = list(map(int, input().split()))  
L.sort()  
ans = 0  
for i in range(N-2):  
    a = L[i]  
    for j in range(i+1, N-1):  
        b = L[j]  
        ans += bisect_left(L, a+b) - 1 - j  
print(ans)  

感想

CodeforcesではAtcoderであまりでないような典型問題がいっぱいあるらしいので、Atcoderが辛くなったらやっていきたいと思う。というか現在進行形でレートが下がり続けているので最近ちょっとつらい。
今日のABC頑張るぞ!!!