■ [others]Xmas Contest 2011 
http://atcoder.jp/contest/26/detail
一風変わった問題楽しいです
- A
- B
- C
- D
- E
- 面白い問題です
- F
- これは！ Advent Calendarの記事で言及した「珍しい制約がある問題」ではないか
- 辺の数は合計N^2のオーダーなのに苦手な辺の数は最大N個しかない
- 苦手な辺はかなり疎にしか分布せず、たいていの場合は普通の辺だけを通って巡回できそう
- ただし1つの頂点に苦手な辺が集中していた場合はどうしても通らないといけない
- そしてそのような頂点を作るには苦手辺のほとんどをその頂点への辺で使ってしまわないといけないから、その条件に当てはまる頂点はたかだか1つしかない
- その頂点に行くために苦手辺を使うのは、コストが1番小さいパスを行ってすぐ戻る場合とコストが1番目・2番目に小さいのを辿るのとの2通りある。合計のコストが小さい方を選ぶ
- この議論はNが小さいと成り立たないので、その場合は現在位置と訪問済み頂点を状態にしてダイクストラする
- Nが大きい場合よりもこっちのNが小さい場合の回答のほうが考えるのも書くのも時間かかってしまった
- G
- 独立に変化するビットをグループ化してマッピングするようなのをうだうだ考えたけどだめだった
- H
- 答えにHが含まれる場合自己言及だなあ、面白い、後でじっくり考えよう
- と思っていたけどその「後」はコンテスト中には来なかった…
- 必ずどれかの問題の正しい出力になっているというあたりに優しさが
- 8問中4問正解+1問部分点
- 10位/100人くらい
■ [SRM]SRM526.5 
http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14762&rm=310932
- 250
- 一番後ろが落とされる場合の回数を数えれば良いんじゃないの、と直感して約√N回のループを書く
- サンプル通ったので提出
- 500
- DPで外側のエリアから順に、0個積もる場合、1個積もる場合、…の確率を計算した。
- そのままだと計算量50*10000*50*10000とかでダメだけど、極端に1箇所に何個も集まる場合の確率は無視できるだろうから途中で切り落とせないか？ と思っていた
- がだめだった
- Challenge
- 250で微妙に違う方針の人が多い。いまひとつどういうつもりのコードなのかわからない
- +50しても順位的にあまりおいしくなさそうなので何もせず
- System Test
- 250は通った
- いまさらになって、この解法ではN-1個目が取り除かれた後にN個目が取り除かれる場合を考慮してない！ 大丈夫なの!? と気づく
- 結果的に大丈夫だったわけですがかなり良くない
- 239.75 + 0.00 + 0.00 + (50*0-25*0) = 239.75
- 59位/614人
- 1933->2023
500は往年の毎回難問だった時代を思い起こさせる感じで良かった
