夏季セミナー参加記

JOI夏季セミナー2014に行ってきました。

参加記を書きます。

 

Day1 (8/25)
  • 新幹線速い
  • じょいしのさんとサブウェイを食べに行く
  • おいしい
  • オリンピックセンターに着く
  • 自己紹介
  • 知らない人がたくさん
  • 交流の予感かな？
  • 本を選ぶ
  • Looking for  a Challenge班に春合宿勢が5人あつまる。交流失敗
  • 今回の宿泊棟は談話室が無いらしい。交流失敗
  • 最近オリンピックセンターの仕様が変わったらしく人権が得にくい。交流失敗
  • Looking for a Challengeの問題(53問)を5人に分ける
  • 私は最後の11問を担当
  • Triangleという問題が簡単だったので解く
  • 問1:有理数がN個与えられるのでどの3つをとってもそれらを辺の長さとする三角形が作れるか判定せよ
  • 問2:整数がN個与えられるのでうまく3つを選べばそれらを辺の長さとする三角形が作れるか判定せよ。作れるならその3つを示せ。
  • 数学っぽい。面白い問題だった。
  • 他の問題もせこせこと和訳をしていく
  • セミナーの時間が終わって夜
  • かかさず見ているHERO(月9)があったのでロビー(唯一交流可能な空間)に行かずに部屋にこもる。交流失敗
  • HEROおわったあとにロビーに言ったら人々が麻雀をしていた。kagamiz氏さんとかOBが遊びに来てた。
  • ロビーが11時に閉まるという残念使用。交流失敗
  • 部屋で11問和訳し終える
  • 寝る
Day 2 (8/26)
  • 和訳が終わっているので問題を解いていく
  • 問題3: Nimっぽい問題
  • やっぱりNimだった
  • Nimへの落としこみでエンバグする
  • あきらめる
  • 問題4: 辺に重みがある連結なグラフが与えられるので、各辺についてそれを使う最小全域木があるか判定せよ
  • Easy
  • 問題5:頂点に重みがあるグラフが与えられるので、全ての互いに隣接している3つ組に対して、その3つのうちの重みの最大値をもとめて、それらの総和を求めよ。
  • 自分で考えて提出すると部分点 (O(M√MlogM))
  • 解説を読むとバリバリのグラフ理論でlogを外していた。
  • 面白い、発表に使おう。と決心
  • 講義の時間
  • 決定木というデジャヴ
  • 少しプログラミングの知識がある中高生にアルゴリズムの講義をするときは数え上げお姉さんを使うという王道でもあるのだろうか
  • 2回目だけどフロンティア法の実装がよくわからない。mate配列による空間計算量はどうするのか
  • ともかく面白かった
  • 一般展開図の個数が行列木定理でも止められるというのはあざやか
  • セミナーに戻る
  • 問題6:整数列が与えられるのである長さkの連続した区間の値が全ておなじになるように値を変更するときに、変更量(差の絶対値)の総和が最小になるような方法を実演せよ
  • メジアンの問題ですね　教育的良問
  • 問題7:整数列S,Tが与えれる。Tの中の連続した長さ|S|の区間のなかで|S|とトポロジカル的に一致するものを全部教えろ
  • うーん　KMPで解けることは聴いたことがあるけど実装したことがない
  • 解説を読むとどうやってKMPに帰着するか書いてある　あざやか
  • しかし今晩CFがあるので組まない
  • セミナーが終わりさっさと風呂に入りCFに出る
  • BGMはキンモクセイのベストアルバム
  • 3問早解きして4問目と5問目を考えてたら終わり　50位
  • レートがあがった
  • 寝る
Day 3 (8/27)
  • 先述の問題7を通す。
  • 問題8:頂点数3Nのグラフが与えられる。サイズ2Nのクリークが存在することが保証されている。サイズNのクリークを一つ挙げよ。
  • うーん　うーん　NP完全じゃないのこれ
  • 解説を読むと自分の頭の硬さがわかる　すごく単純な解答だった
  • 問題9:一般グラフが与えられる。頂点を2グループにわけて、両グループをつなぐ辺を消す。次数が偶数になるような頂点が最も多くなる分け方を一つ挙げよ。
  • うーん　うーん　むずい　頂点数≦200だし典型ではなさそうだな
  • 解説をよむ。　帰納法！　そういえばIOIでもあったなー
  • 問題10:n個のサイコロを振って総和がkになる確率を有効数字2桁で求めよ。
  • シンプルな問題すぎる
  • 有効数字2桁は中心極限定理ゲーだと私は経験で知っている
  • 組む　WA
  • 有効数字2桁の真意は大きいnを調べなくていいということだった
  • 普通のDP
  • 問題11:Aさんは0以上1未満の実数をランダムに9個選びます。Aさんはランダムな順番で１つずつ実数を教えてくれます。あなたは教えてくれるたびにそれがAさんの選んだ数字の中で何番目に大きいかあてなさい。正解率が3.3%を超える戦略を実装しなさい。
  • はぁ？
  • 解かない
  • スライドを作り始める。先ほどの三角を列挙する話をかく。
  • LibreOfficeは忘れた頃にクラッシュする。30枚くらいが消える。つらい
  • 本日分のセミナーは終了
  • 今日はオリンピックセンターで選択をする。選択の待ち時間に法学を学びに来ているベトナム人と、自由に関するカンファレンスに来ているシンガポール人のひととお話したりする。スライドを作っていたらグラフ理論を先行している人に声をかけられたりする。
  • スライド完成！
  • 夏季セミerと交流しないでどうする。交流失敗
  • 一つだけ洗濯物が汚れが落ちきっていなかったので明日も洗濯しようと思う
  • 夜はhogloidさんの部屋に行って「薔薇と髑髏」というゲームをする。キルミーベイベーは面白い。
  • ねむくなったので寝る。
Day 4 (8/28)
  • 起きたら8:30　朝飯1完
  • スライドはできているし暇
  • 午前ずっと寝てしまった
  • 午後は他の人担当の問題をみる。KangaroosとLeonardo numberの解説を読む。
  • この二つの問題はもっとも解説が長い問題だったが、実は作問者回と筆者回が違うので両方載せていた。だから2倍ページが割かれるというからくりだった。
  • Leonardo numberは筆者いわく「私がこの問題に出会った時は数学に関する知識がなかったので解けなかった。作問者から解説を聞いて面白いなと思い自分なりに考察してみたら、想定解より速く実装も簡単な解法を思いついたので紹介するね。」
  • プロ
  • Kangaroosは筆者いわく「この問題はすごく単純な問題だからきっと典型な手法の組み合わせで解けると思ったんだ。そして僕はそういうふうな解き方を思いついた。だけど実は作問者はちょっと複雑だけどもっと速い解法を用意していたんだ。おもしろいから両方紹介するね。」
  • プロ
  • Kangaroosは作問者想定解より筆者想定解のほうが面白かった。
  • いくつかの区間に関するクエリ処理の問題がなんと巡回セールｓ　ゲフンゲフン　ネタバレはよしておこう
  • 面白いやで
  • 寝る
Day5 (8/29)
  • まこりん誕生日おめでとう！
  • みんな発表
  • ちょっと国際交流棟のあの部屋のスクリーンは見にくかったので来年は使いたくないなと思った
  • 我々の班はもうちょっとリハをするべきだと思った（ちょっと見にくいスライドがあった
  • まぁ時間通り終わってよかった
まとめ

楽しかった。運営はちょっとウーンだったけどLooking for a Challengeを見れたのでよかった。