立命合宿2013 3日目

立命館大学の方々による3時間セットでした

チーム決めPhase

ミーティングPhase

  • エディタはCotEditor
  • 言語はC++
  • けしからんマクロは無し
  • 問題読み終わったよ表を作る
  • 私は最初にB問題を担当

コンテストPhase

  • Bを読む。重さをピッタリに合わせる必要があるナップザック問題?
  • @refiute に説明すると、得意そうだったので変わってもらう
  • @ik11235さんのAがWAをもらってしまったので、印刷したものを見せてもらって一緒にデバッグ
  • Cに挑戦する。アローダイアグラムのクリティカルパスの長さを求めれば良いらしい。ある頂点vについて、vに向かう辺の数を予め数えておいて、頂点vに到達したらvから伸びている辺をヒープに突っ込む感じのダイクストラで通した
  • @refiuteにコーダーを交代してもらって、私は適当に問題を漁ってみる。Gは「数え上げおねえさん」でした。M=1,2の場合に限ってパターンが存在するのかな?と思って手計算で数え上げてみようとしたけども、2*4でギブアップ。これじゃあ「数え上げおじさんお兄さん」じゃないか
  • Bが解けたので、次はDに取り掛かることに。とりあえず、評価器を作ることに。@refiuteと私でペアプロしてみました。BNFつよい
  • String#replaceAll的なものを実装している間に、りひゅーとがお手洗いに行ってしまったので、とりあえず1人で実装を進めることに。これが全ての間違いだった
  • 2つの変数をTrueとFalseに置換したときの評価結果から、「変数AはTrueである必要がある」的な情報を得るようなものを作ってみる方針で書きましたが、失敗した失敗した失敗した
  • TimeLimitExceeded

解説Phase

  • Cは解法が多数あって、偽ダイクストラは愚直でバグが少ないけど、計算量、実装量的に劣っているらしい
  • Dは2SATなるものを使うと解けるそうな。構文解析構文解析だけど、ちょっと方針が違ったみたいですね
  • GはDPなんですって。北大のDの方に「数え上げおねえさん」のしおりを頂いたのはフラグだった?ZDDやフロンティア法といった怖い単語がTLを駆け巡っていました

コンテストの感想

  • 最後まで楽しみながら解けました
  • 強連結成分分解のライブラリが必要な問題が2題出題されるなど、チーム内での情報共有が必要とされるような問題セットで非常に教育的でした(ただし、残念ながら私は恩恵を受けられませんでしたが…)
  • スライドがかわいかった丁寧でした

合宿を通して

  • いろんな人と仲良くなれた
  • すごい人のコーディングを生で見れた
  • 今まで敬遠していたアルゴリズムに近づけた
  • またお金をためて行きたいですね