perarduaadastra

競技プログラミングとかをしています

AtCoder Beginner Contest 213 反省

 

結果を鑑みて

1500 26:25

241位。Fが解けそうで解けず、とは言え早解きだったのでレートが上がって黄色になった。

 

A - Bitwise Exclusive Or

A xor B をやる。A問題にしてはやや難しめらしい。

 

B - Booby Prize

ブービー賞ってそういうのなんだ〜って言いながら書いてた。ブービー賞に関する知識がなかったので直感的な正当性証明ができず、少し見直しに時間をかけて提出。

 

C - Reorder Cards

 

坐圧っぽいので、坐圧しようとしたが1次元の坐圧ライブラリしか持っていない。

直観的に縦横は分離して1次元が2つという状況に置き直して良いということがわかったが、証明はなんだか生えなかったので順位表を見た。爆速で通している人たちがいたので恐らく合っているだろうと思って提出。

 

D - Takahashi Tour

木のDFSやるだけ系か、と思った。経路長がどうもそんなに長くないっぽい?(経路をそのまま出力させることから)というところからサンプルを見ながら考えてみると、オイラーツアーそのものだった。

オイラーツアーは非再帰でかけるのでてきとうに書いて通した。それなりの順位だったと思う。

 

E - Stronger Takahashi

 

まあ最短経路系の問題だろうと思った。パンチは2*2マスを縮約して道1マスにする行為かなと思った。いろいろ考えてたら、パンチを2*2マスの自由なマスにワープする操作と捉え直すことができた。この操作ができるかどうかは、一回訪れたマスに2度訪れることが適切かどうかを考えると良さそうで、それを思うとパンチをワープと読み替えることが肯定できる。そうするとワープは今いるマスからチェビシェフ距離2以下のマスから四隅がかけた位置に移動できると言えることになる。定数倍が気になるが、最大ケースを試しているとうまくいくのでOK。

 

この時点で100位くらい。落ち着いてFに進んだ。

 

F - Common Prefixes

Suffix Array感、LCP配列感がある。

考えると、LCP配列でmin(lcp[0], lcp[1], ..., lcp[i]) + min(lcp[1], lcp[2], ..., lcp[i]) + ... + min(lcp[i], lcp[i + 1], ... lcp[N - 1] + N - i が答え。これを求めるのに大変難儀した。

これは遅延評価セグメント木で解けるのでは?と1時間くらいガチャガチャやっていたが、どうもchmin更新とRSQが同時にできるのはSegment Tree Beatsらしい。モノイドチェックの必要性を感じた......

その後BITで寄与を管理しながら計算しようと思ったがうまくいかず終了。

 

これはどうも優先度付きキューのスタック芸みたいなので解けるっぽい。こういうの一回こどふぉで見たんだよなあ......

 

 

G - Connectivity 2

あんまりみてない。 

 

 

H - Stroll

あんまりみてない。

 

総括

順位表見ながら動くいつものムーブをしていたので、今回は飛ばさずいくことになった。ムーブ自体は最近安定している。あとで気付いたことだが、自分のSAはちょっと遅いので整備しなきゃなーと思う。

G, HはどうもARCの中ボス難易度くらいの問題っぽいのでここいらの典型はしっかり押さえていきたい。adhocはABCには出にくそうなのでおいおいその対策もしようね。

Beginner Contest?知らない子ですね。