ABC098
すごく今更ながら前回のABCの結果を。
先に言ってしまうと、前々回に続き二回連続でレートが落ちました。ただ、自分の中ではいいところまでD問題が解けていたのであと一歩かなぁ、と。Aから一応見ていきたいと思います。
素直にといて問題ないはずです。二つの変数にA,Bの値を入力し、その後それぞれA+B,A-B,A×Bを計算します。それが最大値なら、回答用の変数の値を更新し、最後に出力します。
自分のコードはこちらになります。
Submission #2561890 - AtCoder Beginner Contest 098
この問題では、文字列を二つにわけるための仕切りを固定して考えます。まず、分けたそれぞれの文字列において、a~zの文字があるかどうかを判別します。今回は、分けた文字列について、１文字目から順番に見ていき、a~zの存在を判定する配列にそれぞれの文字をチェックしていきました（bool型にしたつもりが、char型になっていました）。最後に、a~zの存在を判定する二つの配列を比較し、どちらの文字列にも存在していたらカウントをします。これらの作業を、すべての仕切りのパターンで行い、最大値を最終的に出力します。
自分のコードはこちらです。
Submission #2562889 - AtCoder Beginner Contest 098
今回は、この問題に想像以上に時間をかけすぎました。解き方としては、B問題と同様に、まずリーダーを固定します。その時に振り向く必要がある人数を調べる…のですが、もちろんC問題なので愚直に調べたのでは間に合いません。そこで、今回は累積和を使いました。int型の配列をひとつ用意して、配列のi番目には、i+1人目までで東を向いている人数を保存しました。これにより、リーダーより右側にいる人は、配列の人数そのまま、左側にいる人は、(左側にいる合計人数-左側で東を向いている人）を調べることで、振り向く必要のある人数がわかります。この方法をとると、O(1)で調べることができます。よって、最終的にリーダーを動かし、O(N)でとくことができます。
この問題の解法はあっさりと思い浮かんだのですが、添え字や、写し間違いのミスで、時間がかなりかかったうえ、ペナルティも重くなってしまいました。自分は実装時のミスや誤字がかなり多く、これが原因で得点を落とす回数がかなり多いので、ここを直せたらいいなぁといつも思っています…
自分のコードがこれです。
Submission #2569370 - AtCoder Beginner Contest 098
今回は500点問題です。自分が過去最低点（Aしか解けなかった）を記録した回のD問題も、xorが絡んだ問題だったので、すごいトラウマでした。結論からいうと、今回も時間中には解けませんでした。しかし、最後の最後であと一歩、というところまでいけたので良かったかなと思います。
この問題を見て数分で、xorが+を超えることがないことは感覚的にわかったので、rを１ずつ増やしていったときに、もし条件に当てはまらなかった場合、それ以降のrで条件に当てはまることはないだろうということに気づきました。それを元に、lを固定して、rをl+1から１ずつ増やしていき、調べたコードを最初に提出しました。
もちろんそれでは時間が間に合わないので、考察を重ねて、いわゆる尺取り法をなんとか思いつきました。自分としては、このアルゴリズムをまだ知らなかったので、これを思いついたのはなかなかではないかなと思っています。
この方法とは、lを固定してrを動かし、r条件を満たさなくなった後、lに1追加する際、rをl+1から始めるのではなく、l=rになるまではrを固定しつづけるというものです。これにより、O(N)でとくことができます。この方法を思いついたのはいいものの、実装を悩んでいるうちにコンテストの時間が終了しました…自分はそのあとも続けて終了後数分たってからついにコードを完成させ、いざ提出！したのですが、結局TLEでした。
原因は、rを固定している最中に、lに1を足した時、l~rの範囲でのxorを計算する方法が、愚直にfor文を用いて計算する、というものだったからでした。xorは、割り算もそのままxorをとればいいという特徴があるので、lを増やす前に、条件を満たさなくなった時点でのxorの値を保存しておけば、そこにl番目の数字のxorをとってあげるだけで、必要な数字が求められるのです。ここを最後に手直しし、ようやくACしたコードが以下になります。
Submission #2571589 - AtCoder Beginner Contest 098
最後に
前述したとおり、何もない状態からあと一歩のところまでいけたところまでは満足しています。ですが、やはりC問題で躓く、実装力や注意力があと一歩足りないのが現状の課題かなぁと思います。もちろん、アルゴリズム力もです。
次のAGCは、AGC初参加なので力試し感覚で出れたらいいなと思います。
今回、初めて自分の解き方の説明をしたのですが、これがかなり難しいです。かなり読みづらいと自分でも思うので、こちらもブログをかいているうちにうまくなったらいいなと思います！
