ラベル 二次元Sparse table の投稿を表示しています。 すべての投稿を表示
ラベル 二次元Sparse table の投稿を表示しています。 すべての投稿を表示

2022年12月28日水曜日

Codeforces Round #841 (Div. 2) and Divide by Zero 2022

 Cまで三完。Eは通したかった。

コンテスト後のツイート

D. Valiant's New Map

 二次元Sparse table(か、二次元セグメント木)でやるしかないと思ってコンテスト中書いたがWA。
 クエリ計算のところで、二点のminではなく、四点のminを取るよう修正したらMLEになりました。

 昔、二次元Sparse tableを書いたときそれだけで数時間かかったことを思えば成長。一旦Sparse tableを取ったあと、そのそれぞれの要素についてもう一度Sparse tableを取ると考えたら、それほど詰まらずに書けました。このままライブラリ化しても良いかも?
 この感じなら、二次元セグメント木も書けそうな気がしてきました。

 ただ、この問題はそういうデータ構造を使わなくても解ける問題でした。毎回二次元累積和を取る解法でAC。

E. Graph Cost

 約数包除くでgcdの個数を列挙した後、大きい方から貪欲にやればOK。
 という解法は分かっていたけど、約数包除の実装でミス。時間がなかったので、ベン図など書かずにこんなものかな、と実装したらダメ。ちゃんと図を描いたら解けました。
 

2020年3月16日月曜日

Codeforces Round #619 (Div. 2)

 Dまでの四完。Dで手間取ったわりに、順位はまあまあでした。

コンテストへのリンク

A. Three Strings

 各indexについて、a[i]==c[i] or b[i]==c[i]

B. Motarack's Birthday

 -1と隣り合っている数字の最大・最小を調べ、その平均で穴を埋める。
 ただし、求めたい、「「隣接要素の差の絶対値」の最大値」は、-1でない二要素によることもあることに注意。

C. Ayoub's function

 fで出力されるのは、「”0”が連続している区間」以外の区間。
 たとえば、"10001"であれば、全部で5*(5+1)/2=15個の区間から、3*(3+1)/2=6個の区間が除かれる。

 なので、1を均等に配置すればfは最大値を取る。そして、そのとき何個0が連続する区間がいくつあるか、が分かれば計算できる。

D. Time to Run

 一筆書きできるのが重要。
 最初気付かなかったけど、絵を描いているうちに気付いた。

 その後は、一旦、一周する命令を書いた後、問題にあわせてどこで切るか決める……という実装がやりやすい。

E. Nanosoft


 けど、考察部分はコンテスト中に大体できていました。データ構造の問題ですね。
 二次元セグ木や二次元Sparse tableに馴染みがなかったため、その後何をすれば良いか分からなかった。

 二次元Sparse tableを使ってどうにかACしましたが、実装も非常に辛かったです。

 普通のSparse tableは理解できるので、やることのおおまかなイメージは分かるのですが、二次元だと、三次元的なイメージがないと全体像はどうも掴めない。
 すぐ、今何を書いているかが分からなくなり混乱しました。

 どうにかACできたものの、もう一回書け、と言われたら辛いです……。二次元セグ木も書かなきゃなぁ。