JOI代表選抜会 Day1, 2
記録だけ。点数開示の流れ。
Day1
- Banner -- Passed System Test 100/100
- Dragon -- Failed System Test 90/100
- Joitter -- Passed System Test 100/100
Day2
- Guess Them All -- Challenge Succeeded 80/100
- Keycards -- Passed System Test 100/100
- Shiritori -- Compiled 5/100
(id:asi1024による)JOI本選予想問題：問題２ 迷子(A Stray Child)
(id:asi1024による)JOI本選予想問題：問題１ 本棚 (Book Shelf)
解法
まあ、パッと見貪欲で終了って言ってもいいけど、詳しく解説してみる。簡単なDPから貪欲にする方針で。
dp[i] := 本棚 i..M を修理するのにかかる最低時間
とすると求める答は dp[1] で、このDPは次のように計算できる。
dp[i] <- infinity
j <- i
while 棚 i..j を1度に修理することが可能である:
dp[i] <- min(dp[i], dp[j] + 1)
j <- j+1
最初は dp[M] <- 1 としておけばいい。
ここで dp は明らかに単調減少だから、1度に修理する棚をできるだけ多くすればいいので、貪欲法で最適解が出せる。
他の考え方(といってもほぼ同じだけど)としては、本棚 1..M を修理する最適解は 1..M をいくつかの範囲に分割したもので表せることから考える。
その最適な範囲の集合の中には必ず 1 を含む範囲があるので、それを出来るだけ広げても集合の要素数が変わらないことから貪欲法で最適解が得られることが示せる。
と、書いてみたけどまあ「パッと見貪欲法」で十分な気がする。
ソース
JOI2010-2011予選
順当にいけば満点。ソース掲載(提出したものとは違うやつもある)。
続きを読むICPC Tokyo/Asia Regional Preliminary Contest
オンライン参加できるらしいので参加。10問中8問解けた。4位らしい。
A
やるだけ
B
i個目までやっていて、直前に右足を使った場合の最小を lr、左足の場合を rl とでもする。i+1個までの lr_next, nr_next を求められるとうれしい。i個目の場所をS[i]とすると
左足S[i+1]、右足S[i]が valid な配置なら rl_next = min(lr, rl+1) 、そうでないなら rl_next = infinity
左足S[i]、右足S[i+1]が valid な配置なら lr_next = min(rl, lr+1) 、そうでないなら lr_next = infinity
で計算するだけ。
C
dp[i][j] := i歩目でポーションの使用状況がjのときに実現可能な最大HP
でDPする。普通に部分集合を列挙してると 1000*3^P で間に合わないので j を大きいほうから回してやって 1個ずつ使うようにする。
D
やるだけ
E
頂点、爆弾と頂点を通る線と多角形の交点、爆弾と頂点を通る線へおろした垂線の足でダイクストラするとできそうだけど幾何は無理
F
左車輪と右車輪を LSpeed : RSpeed に外分する点を中心として回転させることになるのでやるだけ。
G
幾何無理
H
距離でダイクストラしながらできるだけコストの低い辺を採用する。
I
少人数から全部試す。ちょっと前にTopCoderで出た、パッと見二分探索っぽいけど、実際は二分探索はうまくいかなくてたくさんの人がハマった問題と同じ匂いがした。
計算量は結構きつくなるけど、まあそんなにたくさんオペレータは必要じゃない気がするので普通に通る。二分探索は落ちるんだろうか。
J
注文を頂点とするDAGの最小経路被覆を求めればよい。
最小経路被覆の求め方がアルゴリズム・イントロダクションに載ってた気がしたので読んでみたら演習問題として載っていたので解くハメになった。頑張って考えた結果頂点2倍した2部グラフを作って最大マッチング求めるとよいらしい。
JAPLJ Contest まとめと解説
結果
hos.lyricさんが600点(全問完答)で、2位の420点に大差をつけて優勝でした！おめでとうございます！
2位以下は接戦で、上位陣は3完にあとどれだけ点数を上乗せできるかがポイントだったようです。
問題
A, B, C, D, E, Fの6問でした。すべてお花を題材にした問題文になっています。あと、問題IDと問題の名前の頭文字が一致しています。
難易度はA, B, Cが簡単でD, E, Fが難しい、の3：3構成でした。D, E, Fは予想していたよりも皆さんの点が低かったのですが、部分点有りのコンテストの醍醐味を味わって頂けたと思います。
謝辞
素晴らしいコンテスト環境を提供してくれた imos さん、問題のテストや改良に協力してくださった rng_58 さん、問題文の日本語校正を手伝って頂いた kioa2002 さん、ありがとうございました。
↓以下に出題した問題の解説があります
JAPLJ Contest 告知
概要
JAPLJ Contestは今年のIOIで行ったカナダにおいて僕(JAPLJ)が「作った問題が少しずつ溜まっていてコンテストとか開きたい」と言っていたところimosが「それImo Judgeでできるよ」と言ってくれたことで開催が決定した大会です。
基本的にJAPLJが考えた問題を時間内に頑張って解くというコンテストです。奮ってご参加ください。
日時
2010年10月24日(日) 13時00分 〜 16時00分 (3時間)
追記: 夜の部が開催されることになりました。昼の部と同じ問題で、時間は
10月24日(日) 22時00分 〜 翌日01時00分 (3時間)
です。
参加登録は開始数時間前から許可されますが、大会開始後でも参加登録は可能です。
