精進メモ 2021/08/30~
AOJ-ICPC、一進一退です。負けません(今突き放されていますが…)。
AOJ-ICPC
2303 Marathon Match
が
回休憩をしたときに優勝する確率を、全ての
について計算すればよいです。
それぞれが回休憩するときの確率は、二項係数を使って求められます。
そして、そのときにに勝つために行える
の最大値も求められます(
を全探索してもOKです)。
あとは、自分以外の全員に対して勝つ確率を計算して、総和を求めればOKです。
2156 Magic Slayer
AllとSingleでそれぞれ、
だけダメージを与えるために必要なMPの最小値
を計算してあげます。あとは、Allで与えるダメージを固定したときに必要なSingleのMPの総和を計算してあげて答えを求めればよいです。
2534 Dictionary
まずは、接頭辞になっている文字列が後ろに来ている、サンプルの2つ目のケースを潰しておきます。
あとは、文字の種類ごとにどちらが前に来るべきかをメモして、矛盾がないかをチェックすれば良いです。
2177 Champernowne Constant
よくある問題です。
二分探索でスタートする位置を決めて、あとは適当にシミュレートします。
1379 Parallel Lines
傾きで直線を管理します。3点が同一直線上にないので楽に処理できます。
傾きごとに、その直線の部分集合を取った時の、点の集合に対するペアの個数を求めておきます。
あとは、点の集合に対するペアの個数をbitDPでマージしていけば良いです。
1400 Fast Forwarding
ICPC2019の横浜で解いた問題ですが、なんとコードをなくしました。
maxでどの速度にするか、を全部試します。
最低限必須な時間はあらかじめ除外して、残った部分を3進数で計算すればいいです。
ABC217
弊学top2の2人に一生勝てません。
D - Cutting Woods
setに入れて、set上の二分探索をすればOKです。
E - Sorting Queries
一瞬？となったので飛ばしましたが、帰ってきて冷静になるとすぐに解けました。
queue + priority_queueでいいですが、コンテスト中は何故かdeque + mapでやっています。やっぱり焦っていそうですね
F - Make Pair
操作を後ろからみると区間DPできる、というのはどこか別のところでも見た気がします。
区間を二つに分断し、それぞれでの操作をコンビネーションを使って並べていけば良いです。
境界回りがちょっと面倒でバグらせました。
G - Groups
ごとにまず個数を数えます。
すると、番目のグループまで見て、
個のグループになるようなパターン数
というDPをすると、二乗の木DPのような形で計算量がで収まります。それぞれのグループで番号が一番若い人を目印にして重複をなくすのがポイントでした。
もしかしてこの解き方少ないですか？あまり見なかった気がします。
H - Snuketoon
コンテスト翌日にSlope Trickを履修すると、「そのまんまだ…」となりました。
時間の移動はシフト、ダメージはそのまま加算をすればOKです。後ろから見て、最後に原点の値を見てあげれば答えです。
