スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

立命館合宿 2012

日記。
けっこう忘れてしまっている部分もあるけど、簡単に書きます。

Tags : プログラミング OUPC misc
  • 東の人たちと会える機会はほとんどないので、とても有意義だった。
  • 逆に、西の人たちとは事あるごとに会っていて、そろそろ顔なじみな感があった。
  • 僕はわりと人見知りする方だから、stqn さんがちょくちょく話しかけてきてくれて嬉しかった。
  • コミュ力ほしい・・・
  • 運営の方々、問題セットを提供された方々、本当におつかれさまでした。

Day 1

会津の人たちのセット。
lyoz さんと二人で参加。
  • A : いつの間にか lyoz さんが解いていた。
  • B : 僕が読んだ。さすがに二分探索が一瞬で見えたので書いて投げた。
    multiple testcase というのを見逃していて 1WA 出した。
  • C : 問題文が読めない・・・
    C の位置にあるということは読めたら簡単なはずなので、がんばって読む。
  • D : ちょっと実装重めの構文解析だったので、こっちを先に書いた。
    さくっと書けて、サンプルもすぐに通ったので出す。AC。
    first acceptance だったけど、テストケースに小さなミスがあってなかったことになっていた。悲しかった。
  • C が DP っぽかったので書く。どっちが書いたか忘れた。
    ライブをしない場合の遷移を忘れていて、たくさん WA を出した。
  • E : 駅を移動する人の流れが見えて、フローっぽいなーと思って考えていたら最小費用流だった。
    そこまでは良かったけど、グラフを作るところが複雑すぎて、残り時間全部使っても書きあがらなかった。
    深刻な実装力不足。
  • F : ちょっと前に二つの凸多角形を一本の直線で同時に二等分する問題を考えていたので、二分探索はすぐに見えたのだけど、ライブラリが足りなかったので見送ることにした。
  • G : コンテスト中に読む時間はなかったけど、あとで読んでみるととても楽しい問題だった。( 意味深 )

結果は 4 完で、あまりよろしくなかった。
夜に lyoz さんと集まって、半分寝ながら E を通したりしてた。

Day 2

阪大の先輩たちの問題セット。
個人的に好みの問題が多かった印象。

チームは謎の Greedy アルゴリズムによっていつの間にか決まっていた。
rng_58 さんと tokoharu さんと。
勝利を確信した & やることがなくなった。
  • コンテスト開始。
  • 僕が A を書くことに。
  • WA を出して申し訳ない気持ちでいっぱいになる。
  • 紙デバッグしてる間に rng さんが 3 問くらい通していた。
  • やっと A が通って、tokoharu さんと二人で B と C を考える。B の 5000^2 はすぐに見えたけど、TLE 怖いねーということで O(n log n) とかを考えていた。
  • C は DAG にして最大独立集合っぽい何かかな? とか話していた。
  • 結局、求めるものが知ってる言葉で表現できなかったけど、話してる間にパスカバーっぽいなということになって、反例もみつからなかったので rng さんに話してみたら、光の速さで通してくれた。( 誇張 )
  • そのあとは H のデバッグをやっていた。tokoharu さんが大活躍していた。結局、終了の数分前に H が通っていてさすがだった。

Day 3

立命の人たちのセット。
2D さんが強いチームは全完できると言っていたのを僕は覚えています。

lyoz さんと shimejitan さんとチームを組んだ。心強い。
  • A : lyoz さんが担当していてさっさと通していた。あとで自分でも読んでみたら意味不明だった。
  • B : 僕が読んだ。確率を正規化してから期待値の定義どおりに計算すればいい。実装はかなり楽だったのでさくっと通せた。
  • C : shimejitan さんが方針を固めて lyoz さんが書いていた。どうやったのか知らない。
  • うまく並列できていたので、ここら辺ですべての問題が把握できていた。
  • D : 問題文が長すぎて、読解するだけで何度も心が折れそうになった。
  • F : 文字列をいい感じに展開して、あとは適当なアルゴリズムでマッチさせればよさそう、という話になった。展開する部分は、僕が「できる」とか言ってしまった。( ←嘘
  • G : グラフに落として最大流だろうけど、実装重そう。
  • lyoz さんが E が解けそうだというので解法を相談したりしていた。その間に shimejitan さんが Dinic とか Suffix Array とかを打ち込んでいた。
  • E : O(3^n) の前処理 + Greedy でいけそうだということになったのでペアプロした。一発で通った。
  • 時間がなくなってきたので F 一本に絞ることにした。マッチの部分を shimejitan さんが Suffix Array でうまく書いてくれた。
  • 僕が展開する部分を書いていたけど、アルゴリズムが間違っていて RE を出し続けてしまった。最後の数分で修正方法を思いついてがりがり直していたけど、バグが取れなかった。

F が通らなかったのは完全に僕のせいなので、申し訳ない気持ちでいっぱいだった。( 合宿で二回目 )
ただ、役割分担としてはかなりうまく回っていたのではないかと思う。



その他にも、チャレンジ企画とかCキューブでご飯食べたりとか色々あったのだけど、全部は書ききれない。

本当に楽しい三日間でした。
来年以降もずっと続くとよいですね。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。