ABC168
4完でした。
ABC参加3回目にして、初めて緑パフォ出ました。嬉しい。
A問
文字列として受け取って、最後の1文字を切り出して判定する。
n = input()
c = int(n[-1])
if c == 3:
print('bon')
exit()
elif c == 0 or c == 1 or c == 6 or c == 8:
print('pon')
exit()
print('hon')
B問
これも実装するだけですね…。境界値にだけ注意。
k = int(input())
s = input()
if len(s) <= k:
print(s)
else:
print(s[:k] + '...')
C問
各針の先端座標を計算して、三平方の定理を使って距離を出しました。
こういう座標計算はロボット系のプログラムだと頻出なので、見慣れた感があってかなり気楽に実装できました。まさか競プロでロボット系のプログラミングの経験が活きるタイミングが来るとは。。。
コンテスト終わったあと、TLに「余弦定理」というワードが流れてきて、あぁそういえばそんなもんあったな…という気持ちになりました。
from math import pi, cos, sin, sqrt a, b, h, m = map(int, input().split()) theta_a = 2*pi * (h*60 + m) / (12*60) theta_b = 2*pi * m / 60 [xa, ya] = [a*cos(theta_a), a*sin(theta_a)] [xb, yb] = [b*cos(theta_b), b*sin(theta_b)] distance = sqrt((xa - xb)**2 + (ya - yb)**2) print(distance)
D問
グラフの問題だな、というのはすぐに分かったんですが、最短経路問題だと明確に気づくまでは少し時間がかかりました。
グラフ系の問題は全く練習していなかったので、以下の記事をその場で見ながらBFSを実装しました。
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
from queue import Queue
n, m = map(int, input().split())
adj_list = [[] for _ in range(n)]
for i in range(m):
a, b = map(int, input().split())
adj_list[a-1].append(b-1)
adj_list[b-1].append(a-1)
shortest_adj = [None] * n
room_queue = Queue()
room_queue.put(0)
while not room_queue.empty():
room = room_queue.get()
for next_room in adj_list[room]:
if shortest_adj[next_room] is None:
shortest_adj[next_room] = room
room_queue.put(next_room)
can_reach = all([x is not None for x in shortest_adj])
if not can_reach:
print('No')
exit()
print('Yes')
for i in range(1, n):
print(shortest_adj[i]+1)
E問
解けませんでした。
「1000000007っていう数字は れいきゅんのブログで見た！解き方知らね！」となってほぼ諦めムードに。
一応けんちょんさんのこの記事を見たり、自分なりにいろいろ検討してみましたが、「お互いの相性を表す N^2 のテーブルを作って…この時点で O(N^2) で無理じゃん…？」となり、匙を投げました。
あとで解説動画見て勉強します。
F問
E問に無理ゲー感を感じ、試しに覗いてみました。
更に無理ゲーでした。俺にはまだ早い。
振り返り
C問が見慣れた問題設定だったので早く解け、余裕を持ってD問に取り組めたのが良かったです。 あと、前回の計算量オーバーを受け、きちんとコードを見直すようにしました。WAが出なくてよかった。
グラフは隣接リストという構造で持つと良い、というのが今回の一番の学びですね。
次のステップとして、「1000000007で割る」系の問題を解けるようになるのと、BFS,DFSあたりの基本的な探索アルゴリズムをすらすら書けるようになろうと思います。
