出たコンテスト
🤔
IOI2013 Day 2 Virtual
今までやった5時間セットで一番成績がよかった。
100+100+63=263点、Day1と合わせて430点、銀の真ん中らへんなので適正という感じ。
~0:30くらい 1問目を読むと、30分で76点、定数倍が軽ければ100点が取れる解法がわかってしまう。
76点でも取っておいたほうがいいと思ったので実装する。
0:47 1WAを出したが、1問目が通る。にぶたんの区間に気をつけよう。
~1:20くらい 2問目を読むと、よい性質に気づいて一気に90点、定数倍が軽ければ100点が取れる解法が15分くらいで分かる(定数倍ゲー多い...)。
1:50 書いたコードの定数倍が軽かったらしく、2511ms/3000msで通る。
~2:10くらい 明らかに「動的二次元セグ木を書きなさい」という問題だが、闇な気がしたのでやる気をなくす。とりあえずただの二次元セグ木で取れる63点を取ることにする。
2:22 3問目の63点が通る。動的二次元セグ木を導出しようと頑張る気が起きなかったので撤退。(時間が半分で終わってしまった...)
難易度はたぶん8-9-11みたいな感じ。
1問目 Cave
小課題3までは省略。
ドアを左から見ていき、順に対応するスイッチとその正しい状態を当てることを考える。
制約を見るとlogがつきそうなので、二分探索を考える。
「対応が未決定のスイッチの中の左からX個選んだ集合について、今見ているドアと対応するものがあるか？」という問題が解ければ、Xについて二分探索することで答えが求まる。
実はこれは、「左からX個選んだ集合」のスイッチを反転させ、元の状態での質問の答えと比較することで、1回の質問で知ることができる。
クエリ呼び出しはO(NlogN)回、時間計算量はO(N^2logN)となるので、適当な枝狩りをすれば間に合う。
2問目 Robots
実は、最適解において、「弱い」ロボットが運ぶおもちゃを考えると、「Xi>=Xjならば(iが運ぶ任意のおもちゃのW)>=(jが運ぶ任意のおもちゃのW)」が成立することが示せる。この性質を利用する。
解を二分探索することを考えると、「K分以下で片付けられるか？」という問題を解けばよくなる。
まず、「弱い」ロボットにおもちゃを割り当てる。このときロボットiは、「重さXi未満の残っているおもちゃの中で、大きさの大きい方からK個以下」を取るのが最適となる。ロボットをX、おもちゃをWでソートし、尺取り法とpriority_queueを用いることでO(TlogT)でどのおもちゃが取られるかが分かる。
その後は、「小さい」ロボットに、普通に大きさの小さい順に割り当て、最終的に全てを割り当てられたかを判定すればよい。これもO(TlogT)でできる。
時間の最大値がTであることから、O(T(logT)^2)で解けた。
3問目 Games
GCDはセグ木に乗るので、66点までは普通の二次元セグ木を実装すれば取れる。
80点は二次元動的セグ木、100点はそれのメモリ削減が必要らしい。
動的セグ木は、ポインタベースで「ノードが必要になったら作る」ということをすれば書ける。
これを応用すれば二次元にできる。(実装する気が起きない...)
解いた問題
AGC038-C LCMs
https://atcoder.jp/contests/agc038/tasks/agc038_c
Aiの最大値をVとする。今、S(k)=(gcd(i,j)==kなる(i,j)に対するijの和)とすると、lcm(i,j)=ij/gcd(i,j)より、1<=k<=VにおけるS(k)/kの和が答えとなることが分かる。
T(k)=(i,jがともにkの倍数となるような(i,j)に対するijの和)とする。T(k)=(iがkの倍数となるようなiの和)^2 となるので、調和級数より、O(NlogN)で求められる。
T(k)からS(k)を求めるには、余計に数えている分を引く必要がある。実は、kを上から見ていったとき、S(k)=T(k)-(kより大きいkの倍数lにおけるS(l)の和)となるので、これも調和級数からO(NlogN)で求められ、この問題が解けた。
数えなくていい部分も数えているのでAiの和を引いて1/2をすると答えになる。
ABC140-F Many Slimes
https://atcoder.jp/contests/abc140/tasks/abc140_f
Sを大きい順にソートしておく。明らかに、S1が最初のスライムとなる。
時系列順、同じ中では親の大きさ順にスライムを決めていく。
新たにできるスライムの大きさを考えると、「親のスライムより小さいSの中で最大の大きさ」とするのが最適。
もし最大でないものを取ったとして、その後で使われる最大のものとこれをswapしても損しないからである。
これを愚直に実装し、もし途中で構築できなくなったらNo。
CODE FESTIVAL 2016 qual B-E Lexicographical disorder
https://atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_e
SiがSjより辞書順で大きいとき、
1.SjはSiのprefixである
2.最初から見て、2つが初めて相異なるような場所で、Sjの方がSiより辞書順で前にある
のどちらかである。
Trie上で考える。
1.の場合はTrieで前計算することができる。
2.の場合について考える。
「f(i,j,k):Siと他のある文字列Tとの辞書順が決まる場所において、Siの文字がj、Tの文字がkとなるようなTの個数」というテーブルfを前計算しておく。
これはTrie上で、26*O(sum(|S|))程度の計算回数で求めることができる。
各クエリにおいては「Skiより辞書順で小さい文字列の個数」を求めればよい。1.の場合は明らかで、2.の場合は、新しい辞書順でSiの方が後にくるようなfの値のみを足せばよい。
クエリ回答も26^2*O(Q)程度の計算回数で求まるので、制限時間6secに間に合う。
感想
台風のせいで土曜にまともに競プロできなかった、悲しい
