1900に復帰したので明日のARCを頑張る
result:oooooo--(106分(91分+3WA))
perf:2012
rateing:1896->1908
■A - 10yen Stamp
if (x < y)ans = (y - x + (10 - 1)) / 10;
■B - A Reverse
swap
■C - Product
mapで管理するオーバーフローに注意
■D - Count Interval
累積和をmapで管理
■E - Σ[k=0..10^100]floor(X／10^k)
stringで繰り上がりを頑張る
■F - Swap and Sort
読むと只のグラフの問題
頂点番号と書き込まれている番号がぐちゃぐちゃなのでもとに戻す
合計回数を見ると葉から貪欲にやっていけばいい。
不可能なケースは頂点同士が別の木にある時。
n回dfsをすれば良い。
■G - Strongest Takahashi
部分長方形で再起するんでしょ？と思いましたが
Fまでで時間はほとんど使い切りました
n*mの長方形はmax(n,m)で達成できる
1*1の正方形はそのマスが#か.かで0or1
長方形を縦or横で分割して長方形+長方形に分割して再帰。
定数倍は軽い。
■Ex - Manhattan Christmas Tree
並列二分探索というものがあるらしい
問題がもっと単純ならbit上の二分探索で解けるのは明らか
だが、この問題設定だと間に合わない。
なのでどうするかというときに使えることがあるのが並列二分探索らしい
O(log(x) * (nlog(x) + qlog(x)))で解ける。
