ARC 076 D: Built?

http://arc076.contest.atcoder.jp/tasks/arc076_b

解き方

• コストの定義を使って，辺の数をO(N)に削減
• 最小全域木をクラスカルなりプリムなりで求める
  • プリムの場合はpriority_queueを使った実装じゃないと多分間に合わない

ハマった所

• プリム，クラスカルの実装からスタート
  • ライブラリ化した方が良いかも
  • 長くなりすぎるのでそろそろ分割しないといけなそう
• プリムのループ内(最小コストの辺の探索，最小コストの更新の部分)をO(logN)に収める方針を立ててしまった
  • コンテスト内で迷った結果として，よほど特殊な条件でないと筋が悪そう
    • 更新しないといけない頂点が高々1個で，どの頂点か分かるなら，最初にmin_costをソートしておくとO(logN)で収まる？
      • 最小コストの辺は，min_cost[0]で求まるのでO(1)
      • 更新対象を削除したのち，二分探索で挿入場所を決めればO(logN)
  • 最小全域木は辺の数を削っていくのが王道なのかな

ARC 076 C: Reconciled?

arc076.contest.atcoder.jp

解き方

abs(M-N)が2以上，1，0で場合分け．

ハマった所

• 隣接してはいけないので，組み合わせ(nCr)はいらない
  • テストケース通して気づいた
• M+1<Nで場合分けしてた
  • 一度どう解くか紙に書き出したほうが良さそう

活動記録(2017/6/20-6/26)

活動記録(6/20-6/26)

競技プログラミング

ARC 076

結果: 405th, 1123->1198 (パフォーマンス: 1548)

Cで場合分けのミス1回，Dはクラスカルのループ内を条件を使ってO(logN)に収めようとして苦戦． せめてCの実装ミスはなくしたい．

実装

DeepCoder実装

DeepCoderの実装中

実装難易度は比較的低い気がするが，機械学習部分がまだノータッチなのでどうなるか不明．

chainerチュートリアル

DeepCoderの学習目的でchainerに入門中

チュートリアルを一通りやったものの，写経では分からない点も多いので再度

その他

GitHub Wikiの運用開始

ページの階層化ができない等の問題があり，gollumへ移動を計画中

CHI勉強会

参加予定も体調不良で欠席．興味のある分野のまとめは読んだ．