titiaのノート: AOJ

ラベル AOJ の投稿を表示しています。すべての投稿を表示

2022年3月20日日曜日

　20分くらいでAとDの二問だけAC。

　H,Wがそれほど大きくならなそうなので、各見張りそれぞれについて見張っている菱形の境界のマスを通れなくしておけばいいか、と思ったがTLE。

　実際は、imos法を使って高速化することができる。

　ただ、最初に書いた方法でも、O(HW*√HW)くらいなのでは？　高速な言語なら通りそうな気もするけどどうだろう。

　底面が黒マスになるのは、元のマスから向かいのマスへ何回かいったところ、ということは分かったが、判定が分からなかった。

　（+1, +1, -1）を繰り返すということは分かったので、それを使ってどうにかしようとしたのだが偶奇に気付かず。

　ただ、自分が考えた、(+1, +1, -1)を使って絶対値の和を減らしていく……という方針でも解けるはずなので、ACできなかったのは良くないですね。

　ABの二問しか解いていないけど、一応参加。

　解説AC。

　とりあえず、１, ５, ７を取り除いて考えるのはOK。

　そうしたら、6が動けないということに気付いていなかった……。ちゃんと具体例を書いていれば分かったと思うので、面倒がらずに手を動かそう。

　AとC二問の二問しか解いてないけど、一応参加。

　解説AC。

　解かれている人数が多いし、これは解けなくちゃいけなかったけど、全然思いつかなかった……。

・木の問題で、辺に数字が書いてあるとき、ある二点間のpath上にあるxorは、根からの累積xor二つのxorとなる

　というのは他の問題でも使ったことあったと思う。

　使えるようにしたい。