塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

復習 3/16,3/17

atcoder.jp

s = 10**100とかいう良く分からん表現に振り回された感がすごい

やることとしては、いっぱいつなげる方(s)に対し、sのi番目(iは0~len(s)-1、つまりsの各文字)の文字に対して、そこから数えてa,b,c....が次に最短でいつ出てくるかを数える(これをやるときは、sを二つ繋げた文字で考えると良い)。これを前処理として表にしておく。

そして、tの前から見ていって、今見ている文字から次の文字まで何文字あるかな?ってのを、さっき作った表を参考にして調べていく。

言われればははぁんってなるけど思いつかへん......


atcoder.jp

作れない数列の条件(最初が0でない、増加するときに+1でない)はわかったんだけど、数が数えられなかった。

単調増加なら+1、そうでないなら+(要素の値)になる。新規で作るのに要素の値だけの手数が必要になるので、ってことだけどこれ気づかね〜〜〜〜
それっぽいことを考えたけど実装できませんでした。答えは案外シンプルなことが多い。


atcoder.jp

自力ACできたけど、結構ちゃんと条件を押さえないといけなくて教育的だなって思ったので復習

数字iを二進数に直すには、自身より小さい2の累乗の数と&(ビット演算)を取るのが早い(e.g. 24と27は二進数に直すと11000と11011なので、11000&11011は両方のbitが立っている桁のみ1になることから24&27=11000&11011=11000=24となる)
あとNが小さいのでO(2**N)が使える

あとは証言を全部舐めてって矛盾が生じた時点でアウトの処理をすればいいけど、矛盾が出るのは、
①証言者が正直(bitが立っている)かつ、言及先が本当は正直者(bitが立っている)なのに「不親切」と言及している
②証言者が正直(bitが立っている)かつ、言及先が本当は不親切(bitが0)なのに「正直者」と言及している
の2パターンしか存在しないので、この二つを確認すれば良い。