kuretchi's blog

競技プログラミング初心者のブログです。

AtCoder Beginner Contest 061

http://abc061.contest.atcoder.jp/

  • Rank: 364th
  • Performance: 1185
  • Rating: 923 (+44) (Highest!)

3完。

A: Between Two Integers

所感

49s で解けた書けた。過去最速。

B: Counting Roads

解法

隣接行列を使ってカウント。

所感

時間かかりすぎ (12m)。

C: Big Array

解法

(a, b) というタプルのリストを作り、それを a の昇順でソート。0 に b を足していく畳み込みをして、K 以上になった時点で a を出力。

所感

C# で書いた。ソートに使う比較関数を、ラムダ式で渡せるのが便利。C++ でもできるのかしら。(C の高階関数といえば関数ポインタだったけど)。

D: Score Attack

解法

重みの正負を反転させ、Bellman-Ford 法で最短経路探索。

ただし、頂点 1 -> N 間に閉路がないにも関わらず、全体として見たときに閉路がある場合に inf と判定されてしまうので、適当な回数 (> 2N) 更新して最短距離が N 回目以降に更新されたときのみ inf 。

所感

グラフ問題だったので諦めようかと思っていたが、見た感じ典型だったので、蟻本を引っ張り出し写生した。結局 (コンテスト時間内には) 通せなかったが、グラフ問題に手が出始めたので競プロのモチベが向上した。