立命館合宿2013Day2

その他のコンテスト

メモ。

  • 立命館合宿企画者さまとAOJの管理者さまには大変お世話になりました。
  • コンテスト参加者のみなさまと、かなり無理なスケジュールを押し付けてしまったスタッフのlyoz君とfura2君と、インフラ用意してくれたhasi君と、それからついでに自分もお疲れさまでした。
  • 解説 http://www.slideshare.net/oupc/tag/ritscamp13day2
  • 問題文の不備やミスジャッジは今のところ見つかっておらずよかった。一安心だし結構誇らしい。
  • ICPCを意識したコンテストなのでもうちょっと実装よりにしてよかったかも。全体的にアルゴリズム寄りでグラフが多くなってしまった。
  • 序盤の4問には特に思い入れないけど、それ以外の問題はどれも結構気に入っているし思い入れもある。
  • 立命館合宿は夏合宿よりも修行的空気が薄いと勝手に思っていたので、たくさんAC出してもらったほうが気分いいよね、と易しめの問題を序盤に置いといた。参加者のレベル幅が大きいというのもある。でも易しすぎると達成感との兼ね合いもあるので難しい。
  • 難易度調整に関しては自分はやっぱりダメだった。fura2君がかなり正確に難易度把握できていて流石だった。
  • 今回もいくつか使われなかった問題が出た。
    • 重いだけでアルゴリズム的には普通な問題。
    • 完全に知識（ライブラリ）だけで頭使わずに解けてしまう問題。
    • そこそこ面白いけど、元ネタになった問題に類似しすぎている問題。
    • 面白いし好きだけど、残念ながら他のより良い問題とジャンルが被ってしまった問題。
    • 面白いと思ったけど、想定解法が撃墜されてしまった問題。
  • 解説スライド作るのが下手すぎる…。
A:回文数、B:括弧、J:Cube、D:Goto
  • この辺は適当。
  • 回文数は誰でも解けるように。
  • 括弧はちょっとだけ考える実装軽い問題ということで作った。詰まるチームもあるかもなあ、と思っていたけど意外と簡単だったらしい。
  • CubeはPCを遊ばせないようにするため実装寄り。アルゴ寄りのセットという自覚はあったのでPCに触ることすらない、という状況を避けたかった。
  • Gotoは易しめのアルゴ寄り問題ということで。
F:GCD
  • スライドするパートが微妙に難しいので、Oneより難しいと思っていた。
  • 実際は序盤4問以外で最も多く解かれていた。自分としては意外だったけどfura2君は正確にそれを予想していて流石。
I:One
  • IntegralのI。
  • 「数値積分いいよね」+「円とか直線じゃない幾何いいよね」ということで出したい問題だった。
  • 放物線だと不定積分が（幸か不幸か）計算できるので、そっちに引きずられるチーム多そうだと思っていた。
  • しかし放物線以外の山っぽい関数だと交点の計算でニュートン法とか二分探索とか要求することになり難易度上がりすぎるので仕方なくそのまま。
  • 実際にはほとんどのチームが厳密計算していた。
  • 「曲線の公式知らないと解けないのは微妙」という話をfura2君がしていたけど、「FFTとか互除法とかポリアとか数学だけど出てるからいいんじゃない？」と私が言ってそのまま出題された。
L:Trip
  • 作業締切り3~4日前になって、私が突然用意されていた1問を「既出の問題と似すぎていてつまんない」と切り捨てて慌てて作った。
  • Mirskyの定理がDilworthの定理の双対で綺麗＆頑張れば気づけるのでこれで作ることにした。
  • 最長路求めさせるだけだと面白くないので、最長路のクリティカルな辺を求めさせるようにした。結果的にいい感じの難易度に収まってよかった。
  • 半順序集合の言葉を使って問題文表記したかったけど、あまりに不親切なので適当な設定を付けて出題した。問題文長くて不備が不安だったので何度もチェックした。
C:さんぽ
  • 最初はO(n^2*MAX_V)のタイプのナップサックに対応する問題が提案されていた。
  • 個数制限付きナップサックに対応させた方がコーナーケース出てきて面白いと思ったのでそっちに変更に。
E:replace
  • アドホック枠で提案。
  • 提案当時永続データ構造にハマっていて、全部が同じものを参照していたら1箇所書き換えるだけで全部に変更が適用されるの使えそうだなあ、というアイデアから。
  • そのアイデアだけなら簡単だけど、経路圧縮しないと出力でTLEするのは盲点になりやすいと思っていた。
  • 実際、経路圧縮せずにTLEしていた解答は多かった。
  • fura2君と自分で難易度評価に最も差があった問題だけど、実際のAC数を見るとやっぱりfura2君が正しかった。
  • スタックオーバーフローで引っかかっていたチームが多くて微妙に申し訳ない気分になった。
  • アルファベットサイズが小さいことを利用してる人が結構いて興味深かった（本質的には変わらないけど自分では思いつかなかった）。
K:K-th
  • 最初は単に数え上げる問題だった。
  • DPでO(n*A)だなあと思っていたら、ただの2項係数であることに気づいた。
  • 列の問題について、何かの判定ができるときは機械的に辞書順最小求めさせる問題が作れる。
  • それと同じように、数え上げができるときは辞書順K番目が機械的に導かれた。
G:魔方陣
  • 最終防衛レベルの問題という話を聞いていたけど、偏角ソートで区間分割すれば割と単純に解けることが発覚。
  • とはいえそれでも十分難しい。
H:1
  • 最小カットにはまっていた時期に作った。
  • 区間和を累積和に置き換えるテクニック+二部グラフの片方を反転させるテクニックを要求する問題を作ろうと思ったらかなり自然に生まれた。
  • 「問題がシンプル+ぱっと見ではグラフっぽくない+二部グラフであることも一瞬で見えるほどじゃない」という点はすごく気に入っていた。
  • 部分点を設定することができたならw≦6とかで出題したかった。このビットDPも結構面白い。
その他全般的に
  • それなりに経験値得られるセットになったのではないかなあ、と自賛してみる。
  • 去年のOUPC2012はトリッキーというか、飛び道具っぽい問題が多かったけど今年のセットは真面目っぽい。
  • 問題文は各作題者に任せた。
  • 自分担当の分については、今回も短い問題文にした。
  • 問題がシンプルなのに解法は本質的な複雑さを持っている、とか結構好きだし、何より短い方が題意が正確に伝わりやすいし不備がないかのチェックもしやすい。
  • とはいえ、本番では長い問題文を正確に読み取る技術も要求されることがあるので、その練習にならないというのは問題がある。
  • 制約は余裕を持ったサイズに。
  • ジャッジ解は大体制限時間の1/20以下で通るように設定している。流石に20倍も遅い解答の保証まではしない…。
  • スタックオーバーフローで落とすのはあまり好きじゃない(全く本質と関係ないくせにスタック使って展開するのが面倒だから)。
  • なのでLはそれを避けられるようにしている。
  • Eは避けるの難しく、とはいえ10^5というのは微妙なサイズで、書き方や言語で通ったり通らなかったりになる。それは嫌だったので3*10^5にして言語の差によらず一貫して落とすことにした。
  • 余った問題どう処理しようかな…。
追記
  • L問題で、「DAGであると書いてほしかった」という意見を見かけたのだけど、ちゃんと書いてあったような…。有向グラフであることも、閉路が存在しないことも明確に述べていたのだけれど。
  • エスパーしてみると、もしかしたら『「入次数が高々1とは限らない」と明記しろ』ということを主張していたのかもしれない。それならまあ。