AtCoder Grand Contest 034 A,Bの解説

たぶん考察も実装も300レベルかなぁとか勝手に思っています。

Aに関しては解き方はすぐわかったり、BはCPSCOでこんな問題あったよな…となり結構早めに分かったんですが、A問題で4WAしたのが痛すぎた。本当に悔しすぎる…「この冷えの中、どれだけ自分を見失わずに精進ができるか…」というのが試されているのかもしれません。

とかいうのは置いておいて、自分なりの解説です。
Cを解説できるくらいの実力があればいいんですが…

敗因

問題文をちゃんと読んでいなかった
A問題、左右に移動できると勝手に思っていた…これからはちゃんと問題文を読みます…

A - Kenken Race

制約をちゃんと読みましょう。
1マス右か2マス右にしか移動できない。まず、C＜Dのときを考えます(クロスしない)。
最大で2マスしか右に移動できないということは、飛び越えられる岩の限界は1つまで。もし2つ連続して岩があったら、不可能です。for文をaからc、bからdにそれぞれしていくイメージで実装していけばいいです。

次に、途中でクロスしている、つまりD＜Cのときを考えます。すると、途中で順番を入れ替える必要が出てきます。クロスするとき、それぞれの位置関係はA＜B＜D＜Cなので、BからDの間に、「...」のような入れ替わりスポットがある必要があります。なので、あった場合はYes、ない場合はNoみたいな実装をすればいいです。

B - ABC

ABCがBCAになる…ということは、「A」と「BC」が入れ替わる、と考えてもよさそうです。
もうBCだと見にくいので、BCをまとめてXにすることにします。BCでもAでもないものは、/と書くことにします。

ABCACCBABCBCAABCB は、変換(?)すると
AXA///AXXAAX/ になります。AとBCを入れ替える作業を最後まで続けると、
XAA///XXXAAA/ という感じになります。この時点で、/で区切られた部分ごとに回数を計算して足していけばいいと分かります。この入れ替え回数は、「Aから見た時に右にあるXの数」で計算することができます。例えばXAXXの場合だと、Aは2回交換されます。

自分は後ろからXの数を数えていき、Aを見つけた時はans += Xの数として、もし/が来たらX = 0にする、という感じの実装にしました。「Aから見た時に右にあるBCの組の数」でなく、

「BCから見た時に左にあるAの数」をansに加えていってもいいです。たぶんこっちのほうが楽です。substr辺りが役に立ちそうです…(自分は使い方忘れていましたが)。