cafelier@SRM

SRM468

SRM | 00:08 |

SRM468 の成績・ソース (要ログイン) : AC/MLE/- : この過ちは二度と繰り返さぬ…

500開く

• 『都市0番から都市N番まで一直線に順番に都市がつながってます。0からNまで行きたいです。i～i+1の間は陸路だとrt[i]、飛行機で飛ぶとft[i]時間がかかります。離着陸すると危険なので、離陸回数をK回以下に抑えて最短時間で目的地まで行くには？』
  • 要は 0～1 と 1～2 を両方飛行機で行くと 0～2 の一繋がりのフライトとしてよいので離陸回数は1回みたいな
  • N≦40万
  • K≦40
  • 時間は32bitにおさまる程度。答えは64bitになるかも

• 常識的に考えて0～Nまで飛んでいく方が速いだろ…なんだこの問題設定……

• とそれはさておき、
• すごくDPに見える。
• n番目まで、k回の離陸で行く最短時間を dp[n][k] とする
  • 答えは dp[N][0] ～ dp[N][K] の最小値
  • dp[n][k] = 以下の最小値
    • 陸路でnに到着する場合 : dp[n-1][k] + rt[n-1]
    • 0から飛んでnに到着する場合 : dp[0][k-1] + ft[0]+ft[1]+...+ft[n-1]
    • 1から飛んでnに到着する場合 : dp[1][k-1] + ft[1]+...+ft[n-1]
    • ...
    • n-1から飛んでnに到着する場合 : dp[n-1][k-1] + ft[n-1]

• ちょっと待ってこれは O(N^2 K) かかるからダメだ
• O(NK) なら1600万だから想定解だろうなあ
• つまり、do[n][k] のそれぞれの値を定数時間で埋めないといけない
• さっきのやつは
• どう考えてもほとんど同じ ...+ft[n-1] を毎回やってるのは無駄だ…
• えーと、
  • dp[n-1][k-1] が「どっかから飛んでnに到着する場合」だったとすると、
  • それにさらにft[k-1]を足すと、「(n-1)より前のどっかから飛んでnに到着する場合」の最小値が当然出る。
  • 「n-1から飛んでnに到着する場合」は別途計算すればよろし

• つまり、dp[n][k] を求める時の場合分けだけじゃなくて、
• dpの表自体を陸路で着いた場合と飛んで着いた場合に分けて管理した方が表の更新が速い。
• dp[n][k][f] = 都市n番に、k回の離陸で、(f=0 陸路で到着 : f=1 空路で到着)
• とする。
  • 陸路で到着する場合は、１個前の都市に最短で着いてから歩く
  • dp[n][k][0] = min(dp[n-1][k][0], dp[n-1][k][1]) + rt[n-1]
  • 空路で到着する場合は、１個前の都市に歩いて着いてた場合にのみkが変わる
  • dp[n][k][1] = min(dp[n-1][k-1][0], dp[n-1][k][1]) + ft[n-1];

• できた。
• この二つの代入文のまわりに n と k のループを書いて
• n-1 と k-1 を見ているところは n==0, k==0 だと溢れるので、そこだけ分岐して特別処理を埋める
• できた。

• サンプル通った。
• 最大ケースの実行時間も手元で700msec程度。問題ない。Submit!
• あれ、360点台。結構時間喰ってしまった…。

250開く

• スコア表見ると今日も苦戦しているひとが多い
• ってか、問題文ながっ！
• 『とある携帯電話の入力方式で文章を入力しています。キー入力列が与えられるので、どんな文章が入力されたか求めてね。』
  • 方式の詳細は以下の通り
  • 入力: part = {"abc", "def", ...} みたいな9要素の配列
  • "1" を押したら part[1] の文字のどれかが入る。2～9 も同様
  • "0" を押したら半角スペースが入る
  • これだけだと1～9を押したときに何を書いたのか決まらないので、単語ごとに、IMEの変換みたいにして決める
    • たとえば "123#" と入力すると、part[1]+part[2]+part[3] の形の文字列で、辞書順1番目(0-originで)のもの
    • たとえば "123##" と入力すると、part[1]+part[2]+part[3] の形の文字列で、辞書順2番目のもの
    • ...
    • 以下同様。# が多すぎるので、* を入れると # 5個と同じ効果
  • 単語は必ずスペースで区切られてるので
    • "450" だと part[4]+part[5] のうち辞書順先頭のもの+" "
    • みたいな
  • 入力: dict = 50要素以下の文字列配列。これが辞書
  • 出力の長さはたかだか1000文字

• ええと、長いけど、辞書も小さいし、出力も小さいし、地道に実装するだけだよね。
  • 単語 [1-9]+[#*]* 毎にくぎる
  • [#*]* の部分を数値cに直す
  • 辞書を辞書順にソートしておいて、
    • [1-9]+ の部分にマッチするものを先頭から順に探して、
    • c番目を返す

• できた
• よしサンプルも通った。
• まあ特にコーナーケースもないよなあ…
  • ソートされてない辞書もサンプルに入ってるし
• submit!

1000開く

• 『N階建ての建物があります。隣り合う階を何本かのエスカレータが結んでます。ついでに、1階とN階の直通エスカレータもあります。警備員はエスカレータのどっちかの端点に１人配置できます。でも両端に置くとお客様が怖がるのでダメです。できるだけ多く警備員を配置すると何人置ける？』
  • 2本のエスカレータが端点を共有していたりする
    • 入力は、「C階のA番目のエスカレータホールとC+1階のB番目のエスカレータホールが繋がってます」を意味する(A,B,C)の三つ組みのリストで与えられる

• 10≦N≦50
• エスカレータホールの数は全部で100
• エスカレータだけをたどってどこからどこへも行けるようになってる

• テストケースは…
• 最小ケース 10≦N ？なんだこれ。作るのめんどくさいぞ…
  • 10以上じゃないと問題として意味をなさなかったりするんだろうか。
  • 先に少し解き方考えてみないとわからないなー。
  • （※ ここでもっと深く考えておくべきだった…orz）

• まあ、エスカレータホールをnode、エスカレータをedgeとしてグラフを書いてみる。

3F ・　・　　・
   　＼｜　　 ＼
2F 　　・　・　｜
   　／｜／　　｜ ←1Fと最上階を繋ぐスーパーエスカレータ
1F ・　・－－－＋

• これの…なんだろう。
• えーと、できるだけ多く点数を選んで、
• しかも、一つの辺の両端を同時に選んではいけない
• 「最大独立点集合」だ！
• NP-hard だ！

• いやしかし、この「何階建て」グラフは明らかに特殊なグラフだ。
• というかほとんど二部グラフだ
• スーパーエスカレータのことを一旦忘れると
• あたりまえだけど
  • 偶数階のエスカレータホールは奇数階としか繋がってない
  • 奇数階は偶数階としか
• まさに二部グラフ
• ついでに、階数が偶数なら、上と下を直結するエスカレータがあっても↑↑の関係は成り立つので、やっぱり二部グラフ

• 二部グラフなら、最大独立点集合は求まる
  • 頂点の数v － 最大マッチングのサイズm
• だ。
• だったよね。
• ええとググる。うむ確かにそう書いてあるページがひっかかる。
• 一応証明しとこう
  • この値より大きい独立点集合nがあったとする。
    • v-m ＜ n
    • すると、独立点集合に含まれない頂点の個数はv-n＜m個だから、
    • 最大マッチングに関与している2m個の頂点のうち、＜m個しか独立点集合に入ってない点がない
    • 逆にいうとm+1個以上独立点集合に入ってる。
    • でもそれはおかしい。マッチングということは辺で結ばれているはずなので。ダメ。矛盾。
  • 逆に、最低でも v-m 個の独立点はとれることを示す
    • 二部グラフの場合「最大マッチング＝最小点カバー」である
    • 要は、最小点カバーなので、m個の頂点を抑えれば、他のv-m個の頂点は全部繋がっていないようにできる
    • ということで、そのv-m個がまさに独立点集合

• よし

• よくない。Nが奇数のときどうするんだ。

• うーむ。二部グラフではないけど、とても近いんだよなー。
• N階建てだったら、N個のnode集合にわけられて、トーラス状につながってる感じ
• N部グラフと名付けよう。
• こういう場合も、二部グラフと同じで「最大マッチング＝最小点カバー」が成り立ったりするんじゃないか？
• 考える…
• 考える…
• 考える…
• そもそも二部グラフでこの双対性が成り立つのってなんでだっけ…
• ぬぬぬぬぬ…
• わからない

• そもそも「グラフが連結である」という制約が入っているけど、
• これはなんで必要なんだろう。さっきの解法だと使っていないはずだ。
• うううむ。
• 考える…
• 考える…
• 考える…
• わからない

• 「N部グラフ」じゃなくて、「2部グラフなんだけど片側がちょっと微妙に内部でつながってるグラフ」と考えて2部グラフのアルゴリズムを応用
  • 「微妙に繋がっている」部分を同一視して単一頂点に潰して考えるとか。
  • いや、それはダメだなあ。すぐ反例が思いつく
• わからない
• タイムアップ

撃墜タイム

• 500はシンプルなDPだし
• 250は実装問題でサンプルも十分だし
• 落としどころがわからないなあ。

• と思ってたら自分の500がいきなり落ちた
• ええー！
• 落とした人のソースと自分のを見比べる。
• ええとDPなのは同じで…
• そうか、dp[n-1] しかみないから、N*K*2 の表じゃなくて、2*K*2の表でいいのか、賢い。

• ううむ、でも、それ以外に違いはないぞ。合ってると思うんだけど…
• って、これか、違いは！！
• N*K*2*sizeof(long long)はSRMのメモリ制限64MBを溢れている！
• うわーそれは気づかなかった
• 手元だけじゃなくて最大ケースはarenaでテストするべきなのか…めんどうだ…

• いや落ち込んでいる場合ではない、同じミスをしている人がいるはずだ。
• 探さねば…
• 幸い、ICPC でチームを組んでいたので思考の方向をある程度把握できている mayahjp が同じ部屋にいます
• やつはこんなDPでメモリをケチった実装などしないはずだ！open！
• よし N*K の配列取ってる！
• あれ？でも？ N*K*2 じゃないのか。
• へー
• ほー
• それでもうまく書けるのかー。
• ええと最悪ケースはなんだっけ N=10万 と K=40だっけ。
  • 10万×40×8 は … 32MB！足りてる！
  • さらに×2すると64MB行ってしまう。絶妙なバランスだ。無念。
  • (※ …と思ったけど実際には最大はN=40万でした。普通に落とせたのに…！！)

感想

• 500はこれは仕方ない。
• 次から同じことをやらないように対策すればよい。
• というわけでDP用テンプレコードを書き換えてサイズチェックのassertを追加
  • たぶんDP以外で問題になることはないはず…
    • 「速度的には解けちゃうけどメモリ的に解けない」時だけ問題なので
    • 64MBサイズのグラフとか作ったらだいたいのグラフアルゴリズムでしんどそうだし
    • そもそもそれでダメな時にメモリを簡単に減らせるのはDPで１個前だけ見れば済む時くらいだろう
    • しかし一応64MBは気にするようにしよう…

• 1000はwataさんの"N≧10が怪しすぎてすぐ気付けた"を見てやっと気づけた
  • そうだ、確かに言われてみれば怪しすぎる
  • 10階建て以上で、全部で100個までしかエスカレータホールないので、一番少ない階を見れば、10個以下
  • なので、そこへの警備員配置を2^10通り全部試すと、
  • 残りは二部グラフなので解ける
• で、いいと思う。あとで解いてみる。
• 500よりこっちが悔しいなあ。次頑張ろう。次。