5完1WA

各問題

A - Print 341

N 個の "10" を並べた後に一つ "1" を並べます。

いつもコンテスト開始前に、ウォーミングアップと環境のチェック代わりに

int n;
cin >> n;
cout << n << endl;

というプログラムを書くんですが、この cout を消し忘れて 1WA。久しぶりにやってしまった。

番号の小さいほうから大きいほうへの一方通行なので、できるだけ通貨を変換すればよいだけですが、小さい番号からやる方が効率が良いのでそうします。

すべての陸のマスについてそこが「ゴール地点になるかどうか」を全探索すればよいです。ゴール地点になるかどうかなので、与えられた経路の文字列を逆順に、向きも逆にしてチェックする必要があります。

（追記）いや別に逆順にやらなくてもよくないか？と後で気がつきました...

言い換えると、Nの倍数の個数 + Mの倍数の個数 - NとMの公倍数の個数 * 2 が K 以上となる最小の整数を答えればよいです。これは二分探索で簡単に見つけることができます。

1 種類目のクエリについて、L + 1 から R - 1 までの部分はよい文字列であるかどうかの関係性は変化せず、L と L - 1、R と R + 1 との間についてはその関係性は逆転します。

なので、i と i + 1 の関係性がよい文字列なら 0 そうでないなら 1 とした数列で管理すれば、各クエリについて（最大）2か所を入れ替えるだけで済みます。

また 2 種類目のクエリについては、範囲内がすべてよい文字列であればよいので、上記の数列をセグメントツリーで管理して範囲内の和が 0 であるか、1 であってかつ 1 の部分が末尾であれば、よい文字列であると判定できます。

（追記）最後の範囲内の和を求める部分、範囲を一つ狭めれば 0 かどうかだけで判定できることに後で気がつきました...

無向グラフではあるけどコマはWの大きいほうから小さいほうにしか流れないので実質有向グラフであるということはわかるのですが、どの辺を優先して流せばよいかが判別つかず...。

A問題でやらかしをしたけどEまでわりとささっと通せたのでよしとしましょう。