olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

MarathonMatch94

MM94お疲れさまでした。

まず全体的な方針として左上から詰めていく(順列を表すvector(以下ansとする)に前から順番に要素を追加していく)ことにした。

理由としては以下の2点

①どこに一番得点が高い組み合わせを置いても同じだと思ったから。

②左上にそろえることでansにi個目の要素を加えたときに実際に行列を並べ替えやすいと思ったから。

 

あと、Sによって場合分けをした。

S>300のとき、

 

ビームサーチをしようと思ったらめちゃくちゃ時間がかかったので諦めて重みをつけて貪欲を何種類か回して一番スコアがいいものを採用した。

 

S>200のとき、

 

ビーム幅2でansをビームサーチした。愚直にビームサーチをしようと思ったらTLEしそうだったので、遷移は明らかに効率の高いものから1/2~1/20ほど試した。

 

それ以外のとき、

 

ビーム幅~80ぐらいでビームサーチ。愚直に回した。

 

ビームサーチ時には、左上からの累計スコアを鍵にしたが、ansに値が付け加えられるごとに毎回スコアを求めていたら身がもたないので、ansのi要素目まで加え終わったときのできるだけ右の点、下の点の中で左上と連結なものを保持しておき、i+1要素目を加えた際には、それらの点からのみBFSすることによって軽量化ができた。

 

seed 1~10の得点

1:191.83

2:14569.48

3:855662.71

4:114065.16

5:132683:85

6:52594.78

7:212035.44

8:485259.06

9:1312646.12

10:235352.26

 

コードのURL

https://github.com/olphe/MM/blob/master/MM94.cpp

 

IOI列車で行こう(13本選2)

N両の電車とM量の電車が与えられる。それぞれはI列車とO列車のみで構成される。

順にどちらかの先頭の車両を取っていき、IOIOIOIOIのようにIとOか交互に並び、且つIが端にあるように並べたとき、最長の長さを求める問題。

なお、電車はあまらせてもよいし、ぞれぞれ先頭から好きなだけポイしてもよい

dp[Sのi両目][Tのj両目まで使い[長さが偶数or奇数]の時の長さの最大値

をもってDPを回す。

計算量は(N+M)

難易度は6程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2327262#1

JOI国の買い物事情(11本選3)

N個の町、M本の道、K個のショッピングモールがある。

ショッピングモールは町の中にある。

町及び道の中で一番近いショッピングモールまでの距離が最大の値を求める問題。

まず、dijkstraで町までの距離を求め、各辺について辺上で一番遠い点を求める。

計算量はO(NlogN)

難易度は5程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325415#1

ペンキの色(08本選5)

H*Wの看板にN個のテープが貼ってある。色を塗らなければならないスペースが何個あるかを求める問題。

座標圧縮をして、queueで何個あるか探す。

計算量は(N^3)だが定数が小さい。

難易度は7程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325312#1

ぴょんぴょん川渡り(08本選4)

N行に石があり、それぞれの行にある石の数と、位置と滑りやすさが決まっている。

向こう岸まで跳んで行った時の最小の危険度を求める問題。

なお、一行飛びジャンプはM回までできる。

dp[i行目までで][j回までの一行飛びジャンプを使い][i行目のk個目の石]にいるときの危険度の最小値をもって配るDPを回す。

計算量はO(NM)(定数倍が大きいけど)

難易度は6程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325302#1

 

最軽量のモビール(07本選5)

N個の棒があり、そのそれぞれにひもがつながっている。一番上の棒をつるしているひもを除いては、ひもの下には棒かおもりがある。

角棒について、自分をつるしているひもより左の長さ、右の長さ、左につるしている棒の番号、右につるしている棒の番号(おもりなら0)が与えられる。

つり合いを取れるようにし、かつおもりを最軽量化した時の重りの重さの合計を求める問題。

一番上の棒から再帰的に下の棒を見ていき、つり合いがとれていなければつり合うようにし、より軽量化できるなら軽量化する。

計算量わからない。

非情に実装難であると感じたので難易度は8程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325265#1

タクシー(14予選5)

N個の町、K本の道がある。各町にはタクシー会社が存在し、それぞれ決められた数までの道を移動できる。また、料金も決まっている。

1~Nに移動するために必要なコストの最小値を求める問題。

基本的にはdijkstraでよいが、各頂点を訪れるごとに移動できる場所をまとめる。(あらかじめまとめておくとMLEになった)

計算量はO(N^2logN)

難易度は8程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2322477#1