ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状 に参加しました
A-H の8完1:35分で表示上は22位(時間的には25位)でした。
各問題の感想と全体の感想を書いていきます。
問題のリンクはこちらです→ https://www.hackerrank.com/contests/yfkpo2/challenges
C - mosaic tile art
これは
□■■ ■□■ ■■□
をどう並べるか、みたいのをイメージして解きました。
ちょっと視点を変えるパズルみたいでこの難易度帯の中では好きです。
D - n-dwich box
最初は"||"でsplitすることを考えましたが、1-ドイッチの"|"が消滅するので左から順に舐めました。
S = input()
ans = []
cnt = 1
for i in range(len(S)-1):
if S[i] == "#":
cnt += 1
elif S[i] == S[i+1] == "|":
ans.append(cnt)
cnt = 1
ans.append(cnt)
print(*ans)
E - usagi vs kame
制約を見てクエリがソート済みだったので、クエリがくる毎にそれまで動いたうさぎの距離を計算しました。
# list末尾からのpopはO(1)なので逆に並べなおす
S = list(accumulate(A))[::-1]
B = B[::-1]
usagi = 0
for q in Q:
while len(S) and q >= S[-1]: # len(S) == 0の時、and以降は評価されない
usagi += B.pop()
S.pop()
# 結果を出力(省略)
F- mneme game
にぶたんで解きました。Python使う人は https://docs.python.org/ja/3/library/bisect.html#searching-sorted-lists を見ながらbisect, bisect_leftの使い分けを考えるとよいです。
B = [i*(i+1)//2 for i in range(N+1)]
for q in Q:
b = B[bisect_left(B, q)-1]
print(S[q-b-1])
G - double range cards
被さっているところは二回反転させれば操作していないのと同じなので、AとBでそれぞれ反転させました。
二次元累積和の良い典型問題だったと思います。
from itertools import accumulate
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))
R, C = inpl()
V = [inpl() for _ in range(R)]
Q = int(input())
G = [[0]*(C+1) for _ in range(R+1)]
for _ in range(Q):
a, b, c, d, e, f, g, h = [i-1 for i in inpl()]
G[a][c] += 1
G[a][d+1] -= 1
G[b+1][c] -= 1
G[b+1][d+1] += 1
G[e][g] += 1
G[e][h+1] -= 1
G[f+1][g] -= 1
G[f+1][h+1] += 1
G = [list(accumulate(G[i])) for i in range(R+1)]
for j in range(C+1):
for i in range(1, R+1):
G[i][j] += G[i-1][j]
ans = 0
for i in range(R):
for j in range(C):
ans += V[i][j] * (G[i][j]%2)
print(ans)
H - double range cards
ゲームDPですが、N=10でとりうる状態数が十分に小さいので状態をまとめなくても解けます。
ゲームDPに関してはこの解説が好きです。
実装のコツとしては、座標(a, b)からマンハッタン距離mで行ける座標をD[a][b][m] = [(c1, d1), (c2, d2)]のような形で先に列挙しておくと楽です。
# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
N = int(input())
D = defaultdict(list) # Pythonだと多重リストよりタプルをキーにした辞書の方がアクセスが早い
for a in range(5):
for b in range(5):
for c in range(5):
for d in range(5):
D[(a, b, abs(a-c)+abs(b-d))].append((c, d))
G = [[0]*5 for _ in range(5)]
for i in range(5):
row = input()
if "G" in row:
gx = row.index("G")
gy = i
for j in range(5):
G[i][j] = int(row[j] == "B")
C = inpl()
def game(i, px, py, G):
global C
res = []
G[py][px] = 0
if i < N:
for qx, qy in D[(px, py, C[i])]:
if G[qy][qx]:
res.append(game(i+1, qx, qy, G))
G[py][px] = 1 # Gが参照渡し?なのでここで修正しておく
if i%2 in res:
return i%2
else:
return (i%2)^1
if game(0, gx, gy, G):
print("uho")
else:
print("gori")
I - pino assort
本番中に実装が間に合わなかった問題です。 制約をよく見ると
すべてのiについて、v_i, a_i, c_i のうち少なくとも2つが1である
と書いてあるのが重要で、それぞれの味を好む三種類の社員に分類して貪欲で行けます。
解説では箱の数でにぶたんをしていましたが、箱の数は最大でも15*105を越えないので累積和を使って計算しました。
詰まったところとして、1 1 1の社員をバニラ味に振ると1 1 1だらけのケースで少なく見積もってしまったのでアーモンドかチョコ味に振りました。
from itertools import accumulate
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))
N, K = inpl()
V = []
A = []
C = []
for _ in range(N):
v, a, c = inpl()
if v > 1:
V.append(v-1)
elif c > 1:
C.append(c-1)
else:
A.append(a-1)
V = sorted(V)
A = sorted(A)
C = sorted(C)
v = K*1
a = K*1
c = K*1
VV = [0]*(15*10**5)
AA = [0]*(15*10**5)
CC = [0]*(15*10**5)
for i in range(len(V)):
v += V[i]
VV[-(-v//10)] += 1
VV = list(accumulate(VV))
for i in range(len(A)):
a += A[i]
AA[-(-a//7)] += 1
AA = list(accumulate(AA))
for i in range(len(C)):
c += C[i]
CC[-(-c//7)] += 1
CC = list(accumulate(CC))
for i in range(len(VV)):
if VV[i] + AA[i] + CC[i] >= K:
print(i)
break
全体的な感想
良質な典型問題で、前半部分もスピードランとして楽しめました。
12問出題してなにもトラブルなかったのすごくないですか？
— prd🦍 (@prd_xxx) September 14, 2019
しかもオンサイトオンラインともに全完が1人ずつで、幅広い人が2時間フルに参加できたのは満足度が高かったのかなーと思ってます#ゆるふわオンサイト
本当にこれで凄いと思いました。
ただ、J以降もノーヒントで解いてみたかったので、もう一時間あれば……いやオンサイト1位が残り10分くらいで全完したらしいので要精進ですね。
懇親会
ピザをたくさん食べれて嬉しかったです
