ABC058

バチャコン2回目です。

A - ι⊥l

提出コード
そのまんまです。ならYES、そうでなければNOを出力します。
はじめ、YesとNoと出力していて1WAしました…ｗ
問題文はしっかり見ましょう！！

B - ∵∴∵

提出コード
これも、OとEの文字を前から順番に、交互に出力すればOKです。
文字の長さがずれている場合だけ気を付けます。サンプルを両方通せれば問題ないはずです。

C - 怪文書 / Dubious Document

提出コード
最近C問題を0WAで通せない呪いが続いてます…細かいミスをしがちですね。
それぞれの文字列で、'a'~'z'の個数を数え上げ、その最小個数を求めます。
そして、aから順番に最小個数分だけ出力していけば答えが求まります。
最小個数を格納する配列の初期化のときに、配列外を参照するようなコードになっており、REを出しました、危ないので気を付けます…

D - 井井井 / ###

提出コード
考察得意な友人が早々に通していたので、さすがだなぁと思いました。
あるマス目について、そこがいつ選ばれるか(加算されるか)ということを考えてみると、そのマス目よりも上、下、左、右にある辺の中からそれぞれ1本ずつ選んだ時に、そのマス目が1回加算されることになります。ということは、あるマス目は、そのマス目の上下左右の辺の選び方の数だけ加算されます。上下左右の辺の選び方はO(1)で求めることができるので、この方法だとO(NM)で求めることができるわけです。
ですが、問題の制限を見るとこれでは通らないことがわかります。そこで、もう少し範囲を広げてみてみると、 ある行および列において、その中の全てのマス目で縦、もしくは横の長さは同じ値を持っています。そこで、先ほどマス目について考えたことを行、もしくは列について考えてみます。
ある行(列)の面積が加算されるのは、その上下(左右)にある辺の選び方の回数分です。そこで、先にその行(列)の縦(横)の長さを、選び方の回数倍してあげることで、全体をより大きな長方形にしてあげれば、縦横をするだけで答えが求まります(自分の中では、長方形をぐいっと引き延ばすイメージです)。
縦、横はそれぞれ個、個しかないので、この方法なら時間も大丈夫そうです。上下左右の辺の選び方についても考えてあげると、行目の縦の辺の長さをとすると、

がその行の新しい長さになります。列については、をに、をに置き換えてあげれば同様にして求めることができます。
最後に、上記の方法で求めたの和と、の和をかけ合わせれば、答えが求まります。
それぞれの処理ごとに、で割ってその余りをとるのも忘れないようにしましょう。今回は割り算がないので、毎回余りを計算しても問題ありません。


ということで、今回はペナルティ含めて113分ほどで全完達成しました！WAの回数はおいといて、全完自体は昔よりできるようになっている気がします。
順位表と照らし合わせてみると、パフォーマンスも1600でカンストしてるみたいなので満足です！今後も頑張ろうと思います。