2017-05-19から1日間の記事一覧
N両の電車とM量の電車が与えられる。それぞれはI列車とO列車のみで構成される。 順にどちらかの先頭の車両を取っていき、IOIOIOIOIのようにIとOか交互に並び、且つIが端にあるように並べたとき、最長の長さを求める問題。 なお、電車はあまらせてもよいし、…
N個の町、M本の道、K個のショッピングモールがある。 ショッピングモールは町の中にある。 町及び道の中で一番近いショッピングモールまでの距離が最大の値を求める問題。 まず、dijkstraで町までの距離を求め、各辺について辺上で一番遠い点を求める。 計算…
H*Wの看板にN個のテープが貼ってある。色を塗らなければならないスペースが何個あるかを求める問題。 座標圧縮をして、queueで何個あるか探す。 計算量は(N^3)だが定数が小さい。 難易度は7程度に感じられた。 http://judge.u-aizu.ac.jp/onlinejudge/revie…
N行に石があり、それぞれの行にある石の数と、位置と滑りやすさが決まっている。 向こう岸まで跳んで行った時の最小の危険度を求める問題。 なお、一行飛びジャンプはM回までできる。 dp[i行目までで][j回までの一行飛びジャンプを使い][i行目のk個目の石]に…
N個の棒があり、そのそれぞれにひもがつながっている。一番上の棒をつるしているひもを除いては、ひもの下には棒かおもりがある。 角棒について、自分をつるしているひもより左の長さ、右の長さ、左につるしている棒の番号、右につるしている棒の番号(おもり…