コンテストへのリンク
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
アルメリアさんの解説記事を参考にAC。
けど、考察部分はコンテスト中に大体できていました。データ構造の問題ですね。
二次元セグ木や二次元Sparse tableに馴染みがなかったため、その後何をすれば良いか分からなかった。
二次元Sparse tableを使ってどうにかACしましたが、実装も非常に辛かったです。
普通のSparse tableは理解できるので、やることのおおまかなイメージは分かるのですが、二次元だと、三次元的なイメージがないと全体像はどうも掴めない。
すぐ、今何を書いているかが分からなくなり混乱しました。
どうにかACできたものの、もう一回書け、と言われたら辛いです……。二次元セグ木も書かなきゃなぁ。
0 件のコメント:
コメントを投稿