Codeforces Round #434 (Div. 1, based on Technocup 2018 Elimination Round 1)
3完99位
Unratedめ…
A問題
文字列が与えられる。その中に2種類以上の子音が3個並んでいたら切る問題。
切る回数を最小にしたい。
前から貪欲に調べていって条件を満たし次第切ればよい。
貪欲なのでO(N)
http://codeforces.com/contest/860/submission/30422539
B問題
電話番号がたくさん与えられる。それらを連続部分列で識別する場合、各電話番号について一位に定まり且つ最も短い連続部分列を求める問題。
まず全ての連続部分列を求めておく。その後各電話番号について連続部分列を求め、あらかじめ求めたものと見比べればよい。mapで殴る。
O(N(logN)^2)だと思うけど定数倍がでかい。
http://codeforces.com/contest/860/submission/30428030
C問題
たくさんの文字列とその文字列が全体の中で前に来るか後に来るかの情報が与えられる。最終的に文字列を1~Nまでの数字に置き換えつつ並び順も正しくしたい。
まず、数字としては正しいが位置が間違っているものを探し出し、それらを優先的に移動させる。その後、関係のないものを移動させる。
ただし、移動させられない場合は間違った場所にあるものを一度変な名前に変えてやるとよい。セグ木で殴る。O(NlogN)
Ratedだったら+81だったらしいのでつらい…
Codeforces(MemSQL Start[c]UP 3.0 - Round 1)
5完122位でした！すごい！Round2も頑張るぞ！
A問題
本選に25人参加できるコンテストがあり、それらの参加者のうち何人かの予選での順位が与えられる。本選参加を辞退した人は最小で何人かな？
http://codeforces.com/contest/859/submission/30389464
B問題
ブロックがN個与えられるので、それらを並べてできる多角形の周の長さを短くしたい！
基本的には正方形を目指して並べる。欠けていても周の長さは変わらないが、一辺が1短い長方形を作れる場合があることに注意
http://codeforces.com/contest/859/submission/30389970
C問題
パイを順番に配っていく。お互いが最善を尽くしたときに得られるパイの大きさの総計を求める。まず先攻が配る権利を持っている。パイを自分に配ったとき、相手に配る権利が移る。
DP[次に何枚目のパイを配るか][また、配る権利を持っているのはどちらか]
でメモ化再帰を行った。
http://codeforces.com/contest/859/submission/30394617
D問題
トーナメントを行う。各参加者同士では勝率が定められている。i回戦で相手に勝った時、その勝利が発生する確率*2^(i-1)の点を得られる。また、相手が貯めこんでいる点も得られる。どのように進行したら優勝者の持つ点が最大になるかな？
まず各参加者についてi回勝ち残る確率を計算しておき、
DP[i回目に][jが勝ったときの]得点の最大値
を回す。
http://codeforces.com/contest/859/submission/30397238
E問題
席替えをする。各人について今の席と希望する席が与えられる。また、各人は席替え中に席を移動しない、若しくは希望した席に移動する。の二種類しか行動をとりえない。
まず、今の席から希望する席に向かって辺を伸ばし、有向グラフだと考える。
各連結成分についてループが存在しない場合、移動の仕方は連結成分の頂点数通り存在する。ループがある連結成分については、2通り存在する。
それらを掛け合わせてやればよい。
http://codeforces.com/contest/859/problem/E
レート変動は1910->2038でhighestを更新した。やったぜ。
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
