TCO17 Pittsburgh Event / Fun SRM
EasyとMedが通って33位
1573->1565(悲しいね)
Easy 文字列sとtが与えられるので{0,o},{1,l},{m,n}の入れ替えだけでs->tにできるか判定する。
Med 数列が与えられるので、任意の3数の和が9の倍数にならない最大の組み合わせを求める。bitDPをしたがうしさんによると賢い解法があるらしい。
Hard 各深さについて余分に一個頂点作ってベルマンフォード回せばよさそう
CSAcademy#47
4完104位、悲しいね
A 舐めて求める数を数えます
B 何個数字使うかを全探索してうまくいくときに出力する。
C v[i]はnum[i][0]~num[i][W-1]のLCM、u[i]はnum[0][i]~num[H-1][i]のLCM
条件を満たしていたら出力
D 数がNの時は、N/2と(N+1)/2の結果から導き出せるので、再帰的に求める。
なお、必要なNは高々logNなので足りる
悲しいと思ってたらレート上がってよかった。(1781->1785)
CodeForces433(div1)
A 現在の時刻よりも早く出発すべきだった便のうち遅延コストのでかいものから飛ばしていく。自明。
1958->1910
こどふぉ、レート上げるの難しすぎるなあ
Poland Lighting Round(TC MM)
マスがあってチェスのナイトを置く。
あるマスを攻撃できるナイトの数がマスに書かれた数字に近づくようにしたい。
舐めつつ焼きなました。
https://github.com/olphe/MM/blob/master/MM_KnightsAttacks~Randomized.cpp
なんかシステスと競技中のジャッジの性能が違いそうで大量TLEを出して萎えている
現金なのでリジャッジによって息を吹き返した。
温度は頑張っていい感じになりそうなものを調べたんだけどなんか賢い方法あるのかな
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
