Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1413-3ca5b064
この記事にトラックバックする(FC2ブログユーザー)

SRM476 DIV1 参加記録 (この記事を編集する[管理者用])

2010年07月18日01時02分から.

Assignment

250-550-1000の微変則セット.
数分遅れぐらいで参加して,あんまり部屋の様子見てなかったけど,個人的に有名な日本人2人と同じ部屋.
そして,自分以外の赤が居ないという珍しい状況.

EASY

ペットがN種類いて,その中でK匹選んで飼う.
かかるコストは,それぞれa[i]+b[i]*(K-1)で与えられる.
aとbと,支払える最大コストが与えられたとき,最大のKを求める問題.
Nは50以下.

んー.
問題文が分かりにくい.
焦るな,焦るなよ…,僕.
意味理解.(嘘)
K種類飼えるかどうかは,greedyに判定できるから2分探索.
ん,greedyに判定する?
同じ種類のは1匹までしか飼えないの?
飼えない.
じゃ,答えの上限50だから,全部試そう….
がりがり.
書いた.サンプル通った.サブミット.

MEDIUM

ソーシャルネットワークで,各個人のページには,友だち登録してるうちの中からランダムにK人へのリンクが表示される.
K人以下しか友達がいなければ,全員表示される.
N人の友達関係(友達関係はその中で閉じている)が与えられたとき,自分のページから初めて,自分の友達を全部ちょうど1回ずつリンクをたどって辿りつける確率を求める問題.
次に行く友達のページは,達成確率を最大にするように選ぶ.
Nは36以下.おのおのの人の友達の数は高々15.

問題文長い….
取り敢えず,制約を読む.
Nの最大値が36??
2つに分割して全探索みたいなのみたいに2^(N/2)とかになるの?
問題を読む.
DPっぽいけど,普通にやると2^N….
いや,自分の友達だけを考えれば良いのだから,2^自分の友達の数.
でも,50文字の半分ぐらいで最大で25とかありそう.
うーん.
ん?
50ってみなかった気がする.
制約を見直す.
文字列の長さは36以下!
え,それだと,自分の友達の数は最大でも18.
もっと少ないはず,最大でいくらだ?
15.
DPでいける….
書こう.
えっと,複数の人に行けるなら,greedyに行けばいい.
コンビネーションを使って,上位2人は表示されてなくて,3人目が表示される確率とか,そういうのを使う….
書いた.合わない.てか,確率なのに,答えが1超えてる.
うーん.
表示される確率の計算間違えてた.
直した.サンプル通った.サブミット.

HARD

n個の部屋があって,m個の通路があって,通路は船で移動する.
船で移動すると,移動した方向に船が1個移るため,もともと設置された船の数の人数分しか移動できない.
船は,通路の両側にそれぞれ何個設置されてるか与えられる.
部屋0に脱出ポットがある.k人の職員がいる.
職員が何処にいても,部屋0に全員がたどり着けなければいけない.
通路に,最小で何個の船を付け加えれば,全員が0に辿りつけるようになるか求める問題.
不可能ならそれを指摘する.
nとmは50以下.
それぞれの部屋は,高々1個のカノニカルサイクルに属す.
カノニカルサイクルとは,C[0]-C[1]-C[2]-…C[N]がサイクル(C[0]=C[N])だとして,C[0]が最も部屋番号が小さく,C[1]よりC[N-1]が大きい.

うーん,これも問題が読みにくい….
読んだ.
わからない….
カノニカルサイクルとか何だ….
わからない.
うーん,職員の配置の最悪の場合って何.
同じ場所に全員いる場合の気がする.
職員の配置がわかったら,付け加える最小の船の数ってわかるの?
最小費用流!
職員の配置を,どこかに固まっているとして,最小費用流流して,全配置のうち,最悪ケースを返せばいい.
書く.
合わない.
違うよ…,何処にいても脱出できないと駄目なので…,全てのケースを同時に満たさないといけない….
うーん.
このカノニカルサイクルって何だ?
長さ4以上のサイクルは全部これ満たすのでは…?
なるほど,取り敢えず,グラフが木だったらすぐできる.
それは,適当に,0の部屋方向に,kより少なかったら船を配置するだけ.
後は,サイクルの部分は,各サイクルに含まれるノードに職員を集中させて最小費用流流して,最悪ケースを足していけばいいのでは.
本当にいいのか?
わからないし,そもそも実装するような時間が残ってなかった.

Challenge

まぁ,静観するつもりで….
うーん,この250って,答えがNのとき,止まらないのでは…,というか,答えが際限なく大きくなるかRuntime Errorになりそう.
殴ってみる.落ちなかった.
うーん,あれぇ,落ちそうなのになぁ,もうちょっと眺めてみる.
あ,チャレンジが得意なお方に落とされた.
しょんぼり.

System tests

やっぱり自分はチャレンジには向いてないことを再認識するべき.
レートはなんかちょっと上がった.これでも上がるのね….

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1413-3ca5b064
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。