こんにちは。ダイの大冒険ガチ勢のbun913と申します。
皆さんはAtCoderという競技プログラミングに気軽に参加できるサービスをご存知でしょうか？
競プロと聞くと一見とっつきにくいですが、普段プログラミングができないなかでも「あ〜今プログラマーを感じている。輝いている。俺はグラフを探索しているんだぞぉ！！」という気持ちになれるので、とてもおすすめです。
まったく参加したことのない方でも、以下のような記事を見るだけで簡単な問題を解けるようになりますので、興味があればぜひ見てください。
この記事は以下のような1社会人のエンジニアとして、限られたリソースの中でも復習をしつつも、同じレベル帯の方になんらか参考になることがあるかもしれないというモチベーションで書いています。
- 私の状況・現況
- 茶色コーダーと呼ばれる下から2番目のランクづけ
- 競プロ好きだけどつよくない
- 正直数学はできない
- 競プロに全てのリソースを割くことはできない
- ので、公式のAtCoderで強くなるにはのとおり復習だけすることにしました
A - Buy a Pen
考えたこと
- 3つの色の中から一番1本あたりの料金が少ないものを選ぶ
- ただし、使えない色が情報として渡されるのでその色は除外する必要がある
- そのため素直に使えない色に応じて分岐すればいいだけっぽい
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
R, G, B = map(int, input().split())
C = input()
if C == "Red":
print(min(G, B))
elif C == "Blue":
print(min(R, G))
else:
print(min(R, B))
solve()
特に悩むことなく解くことができました。
B - Right Triangle
考えたこと
- 直角三角形を判定するって角度が90度をなす辺があるかどうかを判定すれば良い？
- 「Python 直角三角形 判定」で調べたところ、以下の記事を見つけてピタゴラスの定理を思い出しました
- あとは愚直に実装をしていくだけでした
- 少数を扱うと面倒なので、2乗した値で整数のまま判定でOKです
# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
xa, ya = map(int, input().split())
xb, yb = map(int, input().split())
xc, yc = map(int, input().split())
p1 = (xa, ya)
p2 = (xb, yb)
p3 = (xc, yc)
if is_right_tr(p1, p2, p3):
print("Yes")
else:
print("No")
def ds(p1, p2):
return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
def is_right_tr(p1, p2, p3):
a = ds(p1, p2)
b = ds(p2, p3)
c = ds(p3, p1)
if a + b == c or b + c == a or c + a == b:
return True
return False
solve()
C - Sum = 0
考えたこと(1回目) 不正解
- まず問題のサンプルをノートに書きながらXの候補を考えてみました
- 一番和が小さい値になる数列の候補は要素が全部
L[i]の数列だよな
- 一番和が小さい値になる数列の候補は要素が全部
- ということは、
sum(L) > 0の場合には、絶対に和が0になる数列を作ることはできないよね - そのケースを最初に除外した上で、できるだけ0に近くなるように順番にXの候補となる数列を考えていけば良いのでは？
ということで以下のようなコードを提出しました。
# -*- coding: utf-8 -*-
"""
解く前のメモ用
気づき1
- Lの合計をとった時に0より大きい場合は絶対にNo
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N = int(input())
L, R = [], []
for _ in range(N):
l, r = map(int, input().split())
L.append(l)
R.append(r)
# 絶対に無理な場合を先に弾く
if sum(L) > 0:
print("No")
return
# 極力和が0に近づくように要素を選んでXに詰めていく
# その前にLが大きい順にソートして、Rもそれに合わせてソートする
L, R = zip(*sorted(zip(L, R), key=lambda x: x[0], reverse=True))
X = []
t = 0
for i in range(N):
l, r = L[i], R[i]
# l以上r以下でtに一番近い整数を選ぶ
if t + l >= 0:
X.append(l)
t += l
elif t + r <= 0:
X.append(r)
t += r
else:
X.append(-t)
t = 0
if sum(X) == 0:
print("Yes")
print(*X)
else:
print("No")
solve()
が、このコードはテストケースを通らずダメな実装となっています。
考えたこと(2回目・3回目)
- そういえば、
sum(L) > 0だとダメなのは当然だけど、sum(R) < 0の場合も絶対に和がXになる数列を作ることはできないよなぁ - ここから20分くらい既存の実装を活かせないかもがく
- 既存の実装は一回捨てて「明らかに和が0になる数列Xを作れないケース」の気づきだけ大事にしようと決意する
- それでも「数列の和が0になるように、愚直に数を近づけていく」という発想しか思いつかない
- 「基本的にLとRの真ん中っぽい値を上手く使って、調整できる範囲で調整していく」という発想しか思いつかない
という発想で、本当に愚直に以下のように実装し、正解となることができました。（誤字脱字のコメントが多々ありますが、あえてそのまま残しています。コンテストの中で状況を整理しつつも、急いで書いている息吹を感じますね）
# -*- coding: utf-8 -*-
"""
解く前のメモ用
気づき1
- Lの合計をとった時に0より大きい場合は絶対にNo
- Rの合計をとった時に0より小さい場合は絶対にNo
"""
from sys import setrecursionlimit
setrecursionlimit(10**8)
def solve():
act()
def act():
N = int(input())
L, R = [], []
for _ in range(N):
l, r = map(int, input().split())
L.append(l)
R.append(r)
# 絶対に無理な場合を先に弾く
if sum(L) > 0 or sum(R) < 0:
print("No")
return
# 各区間の中央値をKさん（計算の誤字です）
medians = [(L[i]+R[i])//2 for i in range(N)]
# 各区間の調整可能な範囲をだす
adjusts = [(medians[i] - L[i], R[i] - medians[i]) for i in range(N)]
# 中央値の輪（和の誤字です）を求めて、調整をしていく
S = sum(medians)
if S == 0:
print("Yes")
print(*medians)
return
ad_needed = -S
for i in range(N):
if ad_needed == 0:
break
if ad_needed > 0:
ad = min(ad_needed, adjusts[i][1])
medians[i] += ad
ad_needed -= ad
else:
ad = min(-ad_needed, adjusts[i][0])
medians[i] -= ad
ad_needed += ad
if sum(medians) != 0:
print("No")
return
print("Yes")
print(*medians)
solve()
D - Shortest Path 3
考えたこと
- 隠すこともしていないグラフの問題だなぁ
- しかも「重みつきグラフ」「重みは負の整数ではない」というのが 競技プログラミングの鉄則 という本で学習したダイクストラ法というアルゴリズムが使えそう
- 参考: アルゴ式さんの例題
- ただし、今回の問題の場合は辺に重みがあるだけではなく、ノード自身にも重みを持っているのでそこだけちょこっと工夫すれば良さそう
ということで、以下のようなコードを書いて提出して正解することができました。
# -*- coding: utf-8 -*-
"""
解く前のメモ用
重みあるグラフの最短経路なので、単にダイクストラでとけそう
頂点自体の重みがA[i]で、辺の重みがB[i]となる
頂点1から頂点iまでのパスで、最小の重みを求める
頂点自体にも重みがあるから注意
"""
from sys import setrecursionlimit
import heapq
setrecursionlimit(10**8)
def solve():
act()
def act():
N, M = map(int, input().split())
A = list(map(int, input().split()))
# 筆者追記: 隣接リストという形式でグラフの情報を作っています
G = [[] for _ in range(N)]
for _ in range(M):
a, b, c = map(int, input().split())
G[a-1].append((b-1, c))
G[b-1].append((a-1, c))
# 頂点1からの最短距離を求める
INF = 10**18
dist = [INF] * N
dist[0] = A[0]
# heapqには(重み, 頂点)を入れる
# 筆者追記: ノード（頂点）自体に重みがあるので、頂点1への最小の重みを頂点1自体の重みとして設定しています
q = [(A[0], 0)]
while q:
cur_dist, u = heapq.heappop(q)
if cur_dist > dist[u]:
continue
for v, w in G[u]:
# 筆者追記: ノード（頂点）自体の重みと辺の重みを足して、頂点vへの最小の重みを求めています
path_omomi = cur_dist + w + A[v]
if path_omomi < dist[v]:
dist[v] = path_omomi
heapq.heappush(q, (path_omomi, v))
print(*dist[1:])
solve()
まとめ
- ABC361に参加して、コンテスト中に4問解くことができました
- 私はC問題を絶対解きたい、D問題はできれば解きたいというスタンスで取り組んでいるので、結果だけみれば大満足でした
- D問題やE問題でも「素直にアルゴリズムを知っていれば解ける」という問題がでることもあるので、頻出アルゴリズムを一度実装しておくと後で幸せになるかもしれません
なお今回は目標としていた4問を解くことができましたが、前回はC問題までしか解けなかったものの、復習をすることで新たに知見を得ることができています。
私のような「リソースを競プロにあまり使えない人」こそ、「解けなかった一問だけ解説を見ながら解く」、「もっといい解法がないか解説を見てみる」ということが大事だと感じています。
今後も「楽しいからやる」というスタンスは保ちつつ、自分のペースで下がったり上がったりを繰り返しながら強くなっていければいいなと思います。
以上、bun913でした。ありがとうございました。
Discussion
翌日になって気づいたのですが、C問題は以下のように
取りうる中で最小のXの候補 = Lを起点として、0に近づくまで足していくというやり方がシンプルでよかったです。