blog.bouzuya.net

2020-08-21 AGC034 A, B

AGC034 A, B 考察

AGC034 A - Kenken Race

基本的には A → C と B → D の間に 2 個連続する '#' があると No になる。

C < D のときはふぬけ君 (B 側) を先に移動してからすぬけ君 (A 側) を移動すれば何も起きない。 D < C のときはどこかですぬけ君 (A 側) がふぬけ君 (B 側) を飛び越えないといけない。つまり AB. から .BA になる必要があるので .x. になる箇所が B..=D にないといけない。

添字などつまらないミスを重ねて 3 WA 。

https://atcoder.jp/contests/agc034/submissions/16071405

AGC034 B - ABC

解説 AC 。

変換できる箇所を前から順に探す。変換された場合は変換開始位置 - 1 に移動して続きを探す。実行時間を無視すればこれで最大回数が求められる。この方法で 2 TLE した。

解説を読んだ。

ABC の連続する範囲について BC の左から右に A が移動するような形になる。たとえば ABCBCC なら ABCBCCBCABCCBCBCAC と 2 回移動する。最後の C は連続する範囲を途切れさせている。あとは左から走査して A の個数を数えて BC ごとにそこまでの A の個数を答えに加算する A および BC が途切れたところで A の個数を 0 にする。これを最後まで操作すれば答えが求められる。処理の簡素化のために BCD などに置き換えておくと数えやすい。

個数は大きくなるので i64 などで数えないといけない (2WA) 。

https://atcoder.jp/contests/agc034/submissions/16079560


『銀河英雄伝説 本伝 シーズン 3 』を観た。イゼルローン共和政府の成立まで。


リングフィットアドベンチャーを続けている。レベル 120 。