こんにちは。ダイの大冒険ガチ勢のbun913と申します。
皆さんはAtCoderという競技プログラミングに気軽に参加できるサービスをご存知でしょうか？
競プロと聞くと一見とっつきにくいですが、普段プログラミングができない方でも「二分探索してる。二分探索を使うってすぐにわかるだけで偉い」という気持ちになれるので、とてもおすすめです。
まったく参加したことのない方でも、以下のような記事を見るだけで簡単な問題を解けるようになりますので、興味があればぜひ見てください。
この記事は以下のような1社会人のエンジニアとして、限られたリソースの中でも復習をしつつも、同じレベル帯の方になんらか参考になることがあるかもしれないというモチベーションで書いています。
- 私の状況・現況
- 茶色コーダーと呼ばれる下から2番目のランクづけ
- 競プロ好きだけどつよくない
- 正直数学はできない
- 競プロに全てのリソースを割くことはできない
- ので、公式のAtCoderで強くなるにはのとおり復習だけすることにしました
A - Leap Year
考えたこと and 正解になった実装
- 1583年以上2023年以下ってあるので、やろうと思えば閏年を検索してきて判定してもいけるのでは
- 今回は素直に条件を書いてくれているので、そのまま実装するだけで良さそう
- ただし判定の順番だけ下から上に向かうように書いてあげよう
- 4の倍数は400の倍数でもあるので、先に400の倍数を判定した方が楽
- と考えて無事以下のコードで正解になりました
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
Y = int(input())
if Y % 400 == 0:
print("366")
exit()
if Y % 100 == 0:
print("365")
exit()
if Y % 4 == 0:
print("366")
exit()
print("365")
solve()
B - Second Best
考えたこと and 正解になった実装
- 整数の配列Aの長さはNで、しかもAiの値はすべて異なる
- 素直にAをソートして、後ろから二番目の要素を取得して、その要素が前から何番目の要素かを求めれば良さそう
- そういえばこの前、配列の要素ごとのインデックス番号を取得する便利な書き方を覚えていたからそれでいいか
- ということで以下のコードを提出して正解になりました
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N = int(input())
A = list(map(int, input().split()))
# 要素番号の順にする
order_inds = sorted(range(N), key=lambda i: A[i])
print(order_inds[-2]+1)
solve()
C - Transportation Expenses
考えたこと and 正解になった実装
- 「交通補助額の最大値」を求めるという問題かな
- ということは基本的に10,000円はありえるかな？だめか。じゃあ5,000円はありえるかな？というふうに二分探索で効率よく求めれば良さそう
- ただし、「交通費補助額の上限額を無限に大きくできる場合は」という部分が少しめんどくさそうだ
- 実際それで1回条件式を間違えてしまいました
- あまり難しく考えずに全員の交通費を予算M円以内で賄えちゃうなら、上限を設定する必要がないというくらいの認識に変えると上手く通りました
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N, M = map(int, input().split())
A = list(map(int, input().split()))
# 交通費を無限に大きくできる場合
if sum(A) <= M:
print("infinite")
exit()
max_m = M // N
ok, ng = 0, max_m * 10
while abs(ok-ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, A, N, M):
ok = mid
else:
ng = mid
print(ok)
def is_ok(x, A, N, M):
# x円でN人の交通費を予算M円以内に収められるか
total = sum(min(x, a) for a in A)
return total <= M
solve()
なおこちら使用している二分探索のフォーマットは「めぐる式二分探索」を参考にしています。
これを利用するようになってからバグらせることが明らかに減りました。
覚えておくべきことは、「条件を満たす最大値を求めたい場合はok側の初期値を小さくする」、「条件を満たす最小値を求めたい場合はok側の初期値を大きくする」ということです。
今回は「交通費補助額の上限額の最大値を求めたい」のでok側を小さくしています。
D - AtCoder Janken 3
考えたこと 一度不正解になった実装
- まず「高橋くんは青木くんに1度も負けなかった」という条件から、青木くんが出した手を見れば高橋くんが出した手が2通りに絞られるよね
- 青木くんがグー → 高橋くんはグーかパー
- 青木くんがチョキ → 高橋くんはチョキかグー
- 青木くんがパー → 高橋くんはパーかチョキ
- 次の条件から前の手と一致する手は出せないよね
- じゃあ勝てる時に勝てばいいかな（フラグ）
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N = int(input())
S = input()
win_cnt = 0
last_hand = ""
for i, hand in enumerate(S):
# 青木がグーの時
if hand == "R":
# 前にパーを出してなかったら勝てる
if last_hand != "P":
win_cnt += 1
last_hand = "P"
# 無理ならあいこにする
else:
last_hand = "R"
# 青木がチョキの時
elif hand == "S":
if last_hand != "R":
win_cnt += 1
last_hand = "R"
else:
last_hand = "S"
# 青木がパーの時
else:
if last_hand != "S":
win_cnt += 1
last_hand = "S"
else:
last_hand = "P"
print(win_cnt)
solve()
しかし、こちらの実装では半分以上のテストケースで不正解になってしまいました。
考えたこと and 正解になった実装
- いやまて、なんとなく気づいていたけど「勝てる時に勝つ」だと、全体としての勝ちの回数を最大化できないよな
- だって、高橋くんは1回前に出した手と同じ手を出せないんだから、次に青木くんが出す手も考えずに目の前の勝ちを取るのは後から不利益を被りそう
- 後ろからやっても同じなので、「i回目に出す手とその時の最大の勝ち数」を保持しておかないとダメそう
- それっていわゆる動的計画法だよね
- （しばらく考えて）よくわからんけど、素直に思った通り「i回目に出した手（3通り）を持つ」ように実装しよう
- ということで、以下のコードを提出して正解になりました
# -*- coding: utf-8 -*-
"""
解く前のメモ用
2回目気づき
貪欲じゃだめ。どこで勝ちを拾うかという最適化ができない
動的計画法で最大勝利数みたいなのを考えた方がいいかも
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N = int(input())
S = input()
# i,j i回目まででi回目の手がjの時の最大勝利数
# jが0はグー、1はチョキ、2はパー
dp = [[-1] * 3 for _ in range(N)]
# 初期
for j in range(3):
result = get_result(S[0], j)
dp[0][j] = result
# DP
for i in range(1, N):
# 現在の手
for j in range(3):
# jの手でのジャンケンの結果
result = get_result(S[i], j)
# 1つ前の手
for k in range(3):
# 前の手と同じことは制約的にありえない
if j == k:
continue
# 負けはありえないので0以上で判定
if result >= 0 and dp[i-1][k] != -1:
cand1 = dp[i][j]
cand2 = dp[i-1][k] + result
dp[i][j] = max(cand1, cand2)
# 最大の勝利数
max_wins = max(max(row) for row in dp)
print(max_wins if max_wins != -1 else 0)
def get_result(a, t):
# 0:グー, 1:チョキ, 2:パー
# -1は負けでつまりありえない
if a == 'R':
return 0 if t == 0 else (1 if t == 2 else -1)
if a == 'S':
return 0 if t == 1 else (1 if t == 0 else -1)
if a == 'P':
return 0 if t == 2 else (1 if t == 1 else -1)
solve()
まとめ
- ABC365に参加して、コンテスト中に4問だけ解くことができました
- 私はC問題を絶対解きたい、D問題はできれば解きたいというスタンスで取り組んでいるので、結果としては満足でした
- D問題の動的計画法よりも、個人的には二分探索を解けることに格段の喜びを覚えるタイプなので、Cが解けた時はとても嬉しかったです
私のような「リソースを競プロにあまり使えない人」こそ、「解けなかった一問だけ解説を見ながら解く」、「もっといい解法がないか解説を見てみる」ということが重要だと感じています。
今後も「楽しいからやる」というスタンスは保ちつつ、自分のペースで下がったり上がったりを繰り返しながら強くなっていければいいなと思います。
以上、bun913でした。ありがとうございました。
Discussion