こんにちは。ダイの大冒険ガチ勢のbun913と申します。
皆さんはAtCoderという競技プログラミングに気軽に参加できるサービスをご存知でしょうか？
競プロと聞くと一見とっつきにくいですが、普段プログラミングができない方でも「二分探索してる。ちゃんと二分探索書けているだけでえらい」という気持ちになれるので、とてもおすすめです。
まったく参加したことのない方でも、以下のような記事を見るだけで簡単な問題を解けるようになりますので、興味があればぜひ見てください。
この記事は以下のような1社会人のエンジニアとして、限られたリソースの中でも復習をしつつも、同じレベル帯の方になんらか参考になることがあるかもしれないというモチベーションで書いています。
- 私の状況・現況
- 茶色コーダーと呼ばれる下から2番目のランクづけ
- 競プロ好きだけどつよくない
- 正直数学はできない
- 競プロに全てのリソースを割くことはできない
- ので、公式のAtCoderで強くなるにはのとおり復習だけすることにしました
A - Glutton Takahashi
考えたこと and 正解になった実装
- 連続で
sweetが出ている回数を数えて2回以上なら怪しいよね - 2回以上でもその時食べた料理が最後の料理だったら
Yesそれ以外はNoだよね
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N = int(input())
stroke = 0
for i in range(N):
s = input()
if s == "sweet":
stroke += 1
else:
stroke = 0
if stroke >= 2 and i != N-1:
print("No")
exit()
print("Yes")
solve()
実は2回連続で甘いものを食べた であれば即 No と出力する実装を最初にしていました。
サンプル問題に最後に連続して sweet が出てくるテストケースがあったおかげで間違いに気づけました。危なかったです。
B - Grid Walk
考えたこと and 正解になった実装
- HとW（グリッドの横幅と縦幅）がたかだか50以下であり、移動の指示もたかだか50以下なので素直に言われた通りに移動できるか試せばよさそう
- 移動できる時はこうだよね
- 上下左右の移動の際にグリッドからはみ出ない
- かつ、その移動先のグリッドが
#ではない
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
H, W = map(int, input().split())
si, sj = map(int, input().split())
si, sj = si-1, sj-1
grid = [list(input()) for _ in range(H)]
X = input()
for i in range(len(X)):
x = X[i]
if x == "L":
if sj > 0:
if grid[si][sj-1] != "#":
sj -= 1
elif x == "R":
if sj < W-1:
if grid[si][sj+1] != "#":
sj += 1
elif x == "U":
if si > 0:
if grid[si-1][sj] != "#":
si -= 1
elif x == "D":
if si < H-1:
if grid[si+1][sj] != "#":
si += 1
print(si+1, sj+1)
solve()
C - Minimum Glutton
考えたこと and 正解になった実装
- 料理をできるだけ少ない品数だけ食べたいという謎の状況
- 安酒を大量に飲むのではなく、高級酒を少しずつ飲みたいみたいな気持ちなんだろうか
- 食べた料理の甘さの合計がXより大きくなるか、しょっぱさの合計がYより大きくなると食べるのをやめてしまう
- であれば、単純に一番甘いものから順に並べた場合と、一番しょっぱいものから順に並べた場合の両方を試せば良いな
- 両方試した場合の料理の品数が少ない方が答えになるはずだ
このように考えて以下のようなコードを提出しました。
※ なお実際の業務では使わないような変数名などをコンテスト中には利用しており、あえてそのままにしています。（コンテスト中の急いでいる息吹を感じていただければ幸いです）
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N, X, Y = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# A,Bを大きい順に並び替えた場合のインデックス
order_a_inds = sorted(range(N), key=lambda i: A[i], reverse=True)
# Bを大きい順に並び替えた場合のインデックス
order_b_inds = sorted(range(N), key=lambda i: B[i], reverse=True)
# 甘さの合計、しょっぱさの合計
ama_sum = 0
syo_sum = 0
# コンテスト後追記: ↓Nで十分です。急いでいるので無駄に大きい数にしているのが可愛いですね
cand1 = float("inf")
# まずは甘さから並び替えた順で食べてみる
for i in range(N):
if ama_sum > X:
cand1 = i
break
next_a = A[order_a_inds[i]]
ama_sum += next_a
# しょっぱさの合計
# コンテスト後追記: ↓こっちはNにしてますね。いいから早く通さないと！！っていう意思を感じますね
cand2 = N
for i in range(N):
if syo_sum > Y:
cand2 = i
break
next_b = B[order_b_inds[i]]
syo_sum += next_b
print(min(cand1, cand2))
solve()
D - K-th Nearest
考えたこと（コンテスト中に解けなかったこと）
- 要するに各A[i]の点を数直線上におくよね
- でQの問題で与えられるbからk番目に近い点からの距離を求めるわけだ
- これ以下のポイントがめんどくさいな
- bの点から「距離が近い」点を求めるので、素直にbの点に対するAの配列への二分探索をしても中々うまくいかないぞ
- 全探索で求めるとしたら以下のコードになるけど、これだとO(NQ)で時間内にプログラムが終了しないよねぇ
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B, K = [], []
for _ in range(Q):
b, k = map(int, input().split())
B.append(b)
K.append(k)
# なんとなくマイナスはめんどいので一番小さい数が0になるように調整
minab = min(min(A), min(B))
if minab < 0:
A = [a - minab for a in A]
B = [b - minab for b in B]
# Aはソートしておく
A.sort()
# memo: 絶対間に合わないけどまずは全探索で考えてみる
# 答えはこれであっているけど、O(NQ)で間に合わない
for i in range(Q):
b, k = B[i], K[i]
diffs = [max(a-b, b-a) for a in A]
diffs.sort()
print(diffs[k-1])
solve()
コンテスト後に解説を見て気づいたこと and 正解になった実装
結局コンテスト中に解くことはできなかったので、以下の3分解説を拝見していました。
その中で「k番目に近い点の距離は？」ではなく「距離X以内にk個以上の点がある？」という言い換えをされていました。
また、Twitterなどでも「各B[i]の点を中心にk個以上の点を含む半径を求める」という言い換えを発見して、はっとなりました。
そこで以下のように、「bの点を中心に大きい円を描いていって、k点以上の点が含まれるように円をどんどん小さくしていく」という発想で半径を二分探索することで解くことができました。
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
from bisect import bisect_left, bisect_right
setrecursionlimit(10**8)
def solve():
act()
def act():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B, K = [], []
for _ in range(Q):
b, k = map(int, input().split())
B.append(b)
K.append(k)
# なんとなくマイナスはめんどいので一番小さい数が0になるように調整
minab = min(min(A), min(B))
if minab < 0:
A = [a - minab for a in A]
B = [b - minab for b in B]
# Aはソートしておく
A.sort()
for i in range(Q):
# k個以上の要素を含む最小の半径を求めるというふうに考える
# その半径を二分探索で検索していくとそれがそのまま答えになる
b, k = B[i], K[i]
ok = 2 * 10**8 + 100
ng = -1
while abs(ok-ng) > 1:
mid = (ok+ng)//2
if search(A, mid, b, k):
ok = mid
else:
ng = mid
print(ok)
def search(A, r, b, k):
# rが半径この半径の中にk個以上の要素が含まれているかを探索する
# 二分探索で探索する
l_ind = bisect_left(A, b-r)
r_ind = bisect_right(A, b+r)
return r_ind - l_ind >= k
solve()
なおこちら使用している二分探索のフォーマットは「めぐる式二分探索」を参考にしています。
これを利用するようになってからバグらせることが減ったので、ご興味があれば以下の記事を参考にしてみてください。
まとめ
- ABC364に参加して、コンテスト中に3問だけ解くことができました
- 私はC問題を絶対解きたい、D問題はできれば解きたいというスタンスで取り組んでいるので、最低限はまぁできたという結果でした
- D問題についてキーワード一つで解法が思いついたというのは伸び代だとプラスに捉えています
私のような「リソースを競プロにあまり使えない人」こそ、「解けなかった一問だけ解説を見ながら解く」、「もっといい解法がないか解説を見てみる」ということが重要だと感じています。
今後も「楽しいからやる」というスタンスは保ちつつ、自分のペースで下がったり上がったりを繰り返しながら強くなっていければいいなと思います。
以上、bun913でした。ありがとうございました。
Discussion