AtCoder Grand Contest 036
お疲ら様です。AGCでした。
以下振り返り。
A - Triangle
問題：面積がS/2となる三角形を作れ。ただし各頂点が二次元平面上でｘ、ｙ座標が0以上10^9以下で、整数値を取らなければならない。
考察：
・適当な三角形を買いて、それに外接し、x軸y軸に平行な辺を持つ長方形を考える。
・また単純にするため1点を(0,0)に固定する
・残り2点を、どこかの辺がx軸かy軸と平行、それ以外の2通りで場合分けする。
・そうすると、平行にするときは整数の積で表せないとダメそう
・平行な辺がないときは、長方形の面積から小さい周りの三角形の面積を引き、式を整理する。
・右か下側の点を(x2,y2)、左か上側の点を(x3,y3)とする。ただしここでx2>=x3、y3>=y2。
・面積は(x2*y3-x3*y2)/2となる
・変形するとS＋x3*y2＝x2*y3
・S＋x3*y2を2つの数字の積で表さなければならない。10^18の制約を考えて因数分解も厳しそう。右辺はx2=10^9が最大っぽい。
・以上を頭に入れてヒラメキくんに全てを託すと
S+10＾9の倍数になるよう調整する奴＝10＾9＊S以上になる最小のやつ
という等式が見える。
・左辺は１＊余りにすると余りは10＾9以下になるのでx2>=x3、y3>=y2をうまく満たす
・S<=10＾9のときと、S%10^9==0を処理して終わり
感想：
・等式を求めるまでは良かった。
・最大ケースなど、極端な例を考えて、それに当てはまる構築をしてみる
・今回でいうと、x2を10＾9にとりあえずしてみるとか。
・通した時間はレートに対して遅めだったんですけど、正直難しかった。Bを通せなった方が敗因として近いと思います。
B - Do Not Duplicate
問題：N個の数列aiを、K周追加することを考える。ただし、既に追加した数列に、新しいajと同じ数字があるとき、そこまで全て削除する。
考察：
・サンプルでシミュレーションしてみる。
・すると持ってる数列の一番初めの数字が出てきたらリセットされることがわかる。これは途中の操作は関係ない。
↑これに気づくの遅すぎた。
・順番に、スタートのindexを調べていく。同じindexが出てきたらループがあるので、ループができたら操作終了。indexの種類は高々NなのでN回以内にループがあることがわかる。
・ループの前、ループの2つの部分になるので、K回のうちループの前、ループ、ループの途中までを考えればよい
・ループの長さ*ｘ回、Ｋを減らしておく。Ｋ’とする
ループの前の長さをb、ループの長さをｒとすると
K’=b+(K-b)%r
となる。
・当然K’<=b+rである。また上で調べたリセット位置のリストの長さもb+rであることから、このリストを二分探索して、直前のリセット位置を探す。そして、そこからK’までが求めるべき数列である
・ここで、最後の要素はＮの倍数のindexになることに注意する(これ混乱してミスって通せなかった)
・これをベクトルBとする(ちなみに長さはN以下)
・Bがそのまま答えにはならない。
・どこで部分リセットが起こるかを調べればよい
・ここはちょっと難しい実装でした(後述)
・リセット操作を行ったB’を出力すればよい
実装：
この問題の実装の難しい部分は以下のつである
1．完全リセットが起こる場所を並べる
2．Bの部分リセットがどこで起こるかを考える
自分はそれぞれの数字にindexを昇順に並べたvectorを持ちました。
ホントは二重配列にしたかったんですけど、Aiが最大10＾9なのでって思って見返したら2*10^5じゃん。二重配列のほうが楽です
基本的にはaiのリストを、今の(index+1)%Nで二分探索して、同じ数字を見つける。その次を次回のindexとする。を繰り返します
1は長さNをループするので、二分探索で今のindexより大きい値がないなら、はじめの値を取る。みたいな感じでうまくやります。
自分はindexを％Nと/Nで2つ持って、それぞれを動かしました。
どっちがいいかは好みだと思います。
自分のやり方だと、コード上の操作は増えちゃうんですけど、二分探索をするときと、値更新するときにindex処理が楽になるという利点があります。
もっと言うと％Nで二分探索→動く量を求める→足すみたいなのがない。
同じような操作で2もできます。繰り返しがないのでめっちゃ楽。
なんやかんや実装して、頑張ってバグ取りすれば通ります
感想：
・反省１：完全リセットに着目するとよいことに気づくまでに時間がかかった
・反省２：最後のBの処理で、こんがらがって時間食った
・反省３：lower_boundがうまく使えずバグ取りができなかった
・まず１は仕方ない感ありました。強いて言うなら、無限に繰り返すところでシミュレーションするとかでしょうか。コンテスト中に気づけただけでもいいかもしれません。
・次２、いやここはひどかった。問題文通りの追加する、削除するに惑わされたのが良くなかったです。なんか色塗りDPっぽい考えしたら前から見ればいいことに気づけました。これもコンテスト中に気づけたのでまあ。どうにか時短するのがこれからの課題ですね
・最後３。実装力のNASA。upper_boundとか使ったんですけど、lower_bound固定でいいかも。
・最近強く感じる悪いところが、いま整数値を扱っているのか、indexを扱っているのかが混ざることですね。1足したり1引いたりして調整するのをミスってバグるみたいなパターンが多い。
・解決策として、添え字をわかりやすくする。自分ルールを丁寧に決める。みたいなところでしょうか。
・デバックのやり方。一回提出して弾かれたとき、はじめから丁寧にコメントつけつつ見直すべき。実際にコメントを書く必要はないけど、それくらいの気持ちで見直さないとダメだと思いました。コメントつけると自分の頭の中の論理が整理されるのもありますしね。
C - GP 2
900点問題なのと、通してる人が多いわけじゃなかったから問題文すら読んでないです。
なんかBとあんま変わらない（Bより簡単？）という意見もあったので近々触りたいです。
総評：
・考察の方針はあってたし、Bを通せれば青パフォは出てたと思うので、難問を(まあまあ)早く通す練習が必要ですね
・700を本番で考察実装進められたのは成長だと思っておきます
・最近のコンテストは冷え冷えなのでそろそろABCあたりで暖まりたいところ…。早解きより6完できるようになりたいね。
