cafelier@SRM

SRM430 Div1

SRM | 04:26 |

SRM430 の成績・ソース (要ログイン) : AC/AC/TLE : ダメとほぼ確信しててsubmitするのはやめた方がいいのかな

250 開く

• 『xとkが与えられますx+y==x|yになるようなk番目に小さい正の数yは？』

• えーとxのビットが0の所にk-1のビットパターンを埋めていくだけじゃないかな

• 普通に埋めた。
• なんかでかい。x+yすなわちx|yの値を返してた。バカか。yを返すように変更

• ちょっと違う
• y>=0じゃなくてy>0なんだからk-1じゃなくてそのままkのビットパターン埋めるだけじゃん
• サンプル通った。submit

500 開く

• 『2次元平面上に都市がN(<=10)個くらいあって、マンハッタン距離D以上離れてる都市ペアを姉妹都市とできる。それぞれの都市は最大M(<=3)個以内の都市と姉妹都市になれる。できるだけたくさん姉妹都市ペアを作れ。』
  • 複数作り方がある場合は距離の和が最小なのを。

• えーとグラフでも書いてみる。左に都市1～10、右に都市1～10、距離D以上の都市間に線引いて、距離をコストにして、sinkの容量でM以下という制約を表現…
  • 最小費用流？うわーバグりまくってる自信のあるライブラリしか手元にないなあ怖い
  • って違うよ！なんで都市が分裂してるんだよそのグラフ。ローマ分割じゃあるまいし！
  • そもそも500で最小費用流は難易度的にないだろう…

• ちゃんと分裂させないで書いてみよう。それでもなんかマッチング系のになるんじゃないか？
• ならぬ…

• 落ち着こう。

• 都市は10個しかない。くっつく都市数は3しかない。
• 全探索するとどうだ。1番の町を他とくっつけてみて、次に2番の他とくっつけてみて…っていう。
• 10C3は…120、9C3は…84、8C3は…56、ちょっとこれこの先掛け算してくと厳しい数になるなー
• しかも10C3よりもっと多いよな。2個だけ繋げるとかいう可能性もある。

• わかんないーーーーーーーーー。

• いや待て。メモ化できないかな？？？？？
• 上の全探索を書くと

 rec( i:次繋げる都市番号, v:残りくっつける都市数リスト ) {
    [i+1 .. N) から v[i] 個以下(距離D制約を見たしつつ)都市をえらぶ選び方全部試してみる
 }

• こうなるはずだ。
• ところが「残りくっつける都市数」のリストは 0～3 が 10 個並ぶだけだから、4^10=2^20=1Mだ。これは行けるサイズだ。これだ！

• というわけでこの探索を「残りくっつける都市数リスト」でメモ化
• 0～3個取る取り方をループで書くのがめんどうだったのでハイパーコピペタイム。すみませんすみません
• サンプル通った

• サンプルに9都市の例しかなかったので、念のため10都市でD=0でM=3にしてみた。630msとか。OKOK。
• Submit

1000開く

• 『キャプテン1号とキャプテン2号が海賊軍団のチーム分けをする。各海賊の1号さんから見たスコアと2号さんから見たスコアが与えられたとき、人数均等な分け方で２チームのリーダー視点スコアができるだけ近くなるようなチーム分け求めてね』
  • 同点の分け方がある場合は辞書順最小(番号の若い海賊を1号チームに回す方)を返す
  • 海賊さんは最大36人。個々のスコアはlong longには十分おさまる程度のデカさ
  • ちなみに問題文には海賊とかどこにも書いていないのですがキャプテンという単語を見たら何故か私の脳内でそう変換されていました。

• （人数均等に分けるという条件を最初まったく読んでなかった。）
• とりあえず、2人のキャプテンのスコアを完全に揃えるとPARTITIONだな。てことはNP-hard。

• 普通にPARTITIONに帰着できるんじゃないかな？
  • 最初全員2号チームに回したと仮定すると、sum(score2)くらいチーム2が得している状態
  • ここで各人員をチーム1に回すと score1[i]+score2[i] 是正される
  • てことは s[i] = score1[i]+score2[i] な集合 s の部分和で sum(score2) にできるだけ近づけたのが解
  • これはPARTITION。

• っても、個々のスコアがでかいから擬多項式時間のDPは無理だよなー。
• 36人ってことは枝刈り探索でPARTITIONってこのくらい間に合うものなのかなー。てかそれしか無いよなあ。書こう

• 書いた。辞書順にトライしてってそれまでのベストスコアで細々枝刈り
• 最後のサンプル通らない

• なんで？ああ、人数均等に分けなきゃいけないのか！

• 探索の枝刈り条件をごにょごにょいじって均等という条件つけたし。
• サンプル通った

• 最悪ケースをためそう。36人いるやつ。

• まあ当然遅すぎて終わらない

• うわーあと2分しかない！！！！
• ええい、スコア差0に分ける分け方が見つかった場合はそこで探索打ち切るコードを入れたらさっき手で2,3個作った36人ケースは全部数百msで通った！駄目元で出してしまえ！うりゃー
• (※Challengeされて死亡)

感想

• 500はみんな1<<20のビットにvをエンコードしてた。そりゃそうか。ふむふむ。

• 1000は結局どう解くのが正解なのかなー。明日考えよう。人数もピッタリ均等に分けるというのがポイントなのだろうか。
  • あるいは、自分のコードは明らかに自明な枝刈りが2,3個足りてないのでそのせいだったとか…そんな甘いことはないか。

• こういう、有名問題をちょっとだけ捻ったのが解けないのは悔しいなあ
• あと観測範囲のみなさんChallenge巧すぎる。コツが知りたい
  • (追記)
  • http://shinh.skr.jp/m/?date=20081221#p03 shinhさんのChallengePoint！
  • http://d.hatena.ne.jp/chokudai/20081221/1229848089 chokudaiさんのChallengePoint！