いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Beginner Contest 061(ABC061)

AtCoder Beginner Contest 061 - AtCoder Beginner Contest 061 | AtCoder
出ました、結果は3完、Dは解けるかと思ったがだめ、Cはもっと早く解きたかった
友達と大学のスペース使って出たのでとても楽しかった
なんだかんだ誘ったらみんな出てくれて刺激的で向上心がグイグイでうれしい

A.Betwee Tow Integers
整数CがA以上かつB以下であるかを判定
YES,NOじゃなくてYes,Noだったのでちょっと危なかったが普通にAC

B.Counting Roads
N個の都市とM本の道路が与えられる
各都市が持ってる道路の本数を順番に出力していく
すぐに書こうと思って気が付いたらsetをincludeしていた
何かがおかしいと一旦落ち着いてvectorに数え上げて入れていったらAC
特にどの都市とどの都市がつながっているとか考える必要がなかった
が、問題文からはちょっとわかりにくかったので冷静に考えれてよかった

C.Big Array
数字と個数がたくさん与えられるのでn番目に小さい数字を出力する
制約見ていけると思って全部vectorに突っ込んだらREの嵐が吹き荒れた
何故いけると思ってしまったのか
格納しないなら実装地味に難しいなぁって思っていろいろ考えたけどmapが丸いと思って書いた
個数を足していってkを超えたらその時の数字を出力するだけだったのでちゃんと考察すれば実装も簡単ですぐできそうだった
制約の1≦K≦b1…+…bnの部分が最初意味が分からなかったがよく読めばこれはbの総和であり、桁数が指定されていない
実際このkはintでは収まらずそこに気づくまでにかなり時間をロスしてしまった

D.Score Attack
N頂点M辺の重み付き有向グラフがある
1から移動を始め、通った辺の重みがスコアとして加算され、ゴールのマスでゲームを終了してもよい
スコアが最大になるときのスコアを出力、同じ辺を通ってもいいので無限に増加するならばinfを出力する
なんでもいいから全探索を2回行ってスタートからゴール、ゴールからゴールの最高スコアの経路を求めようと思った
分岐はそれほどでもないと思ったが全探索をどうするかでとまどってる間にタイムアップ
後で友達に聞いたら名前だけ聞いたことあるベルマンフォードを紹介され、更に最大値は正負逆転して最短経路にすればいいと教えてくれた
実装力も足りないと思ったしどのみち解けてなかったようだった

全体を見るとCでのタイムロスがとにかく痛かった
もうすぐABCのABが埋まるのでCとARCのAを中心に埋めてアルゴリズム力も養っていこうと思った