132. AtCoder参加記録（AtCoder Beginner Contest 266）
35回参加でレート 1386 です。
今回はパフォーマンス 1149 です。
ABCDを通して、EFGExは未解答です。
各問題の思考過程など。
A
56秒。やるだけ。
B
3分38秒。
となる条件を満たす数を見つければよいので、
を初期値として適当に足したり引いたりするようにしました。雑に書きましたが、思ったより重くてちょっと反省。
C
11分13秒。
問題を読んでガチガチの幾何問が来たことに驚きました。
- 3点で三角形を作ったときもう1点が三角形内部にあるとダメなような気がする（未証明、直感）
- 三角形の外部・内部判定ってたしか外積で出来たような…。分からんのでググる
- ググって出てきた三角形の内部判定をそのまま書き下し、点の組み合わせ全てを試す感じに
D
9分45秒。
- 移動速度の記述理解にやや時間が掛かったが、要するに1つ隣へ行くかその場に留まるか、ということか
- 同じ時刻・同じ場所においてスコアが最大となる手が明らかに最適なので、これだけ残して探索すればよい。ここからDPっぽさを感じる。
で場所が5箇所しかないから行ける。
E
解けず。最初そもそも問題を誤読していた…。
- 色々よく分からない考察をする（何考えてたか覚えてない…）
- 1回だけサイコロを振るなら出目の期待値は 3.5 なので、3以下なら振り直すのがよい
- じゃあ出目が3以下なら振り直し続ければよいのでは？と考えるが入力例3が合わない
- 何もわからないのでFへ…
F
解けず。Eよりこちらの方が見込みありましたが、Eで気持ちが落ちていて最後まで詰めきれなかった感が強いです。
- 木に1本だけ辺が追加されたグラフなので、閉路的なものが1つあるグラフになる（ここで何故か閉路を構成する頂点が3つだけだと思い込む）
- 閉路を経由する必要があるときだけ単純パスは一意に定まらない
- 閉路を経由する必要が無いのは、閉路を構成する頂点で最も近いものが等しいペアの場合
- DFS・BFSをゴチャゴチャやって閉路を構成する頂点集合を特定し、そこに含まれる各頂点から全頂点への距離を出しておけば、クエリに
で答えられる（閉路を構成するのが3頂点だけだと思い込んでおり、これで間に合うと考えていた）
- かなりの時間を掛けて実装し、入力例1は合うが2が合わない。デバッグすると閉路を構成する頂点集合は3つより多い…。少し考えて、3つに限らないことに気付く。
- 今の実装を少し変えて何とかならないか考えたが、明らかにTLEするしもう時間も無いので諦め
G, Ex
見てないです。
Dまでのスピードは良かったですが、E・Fともに考察で詰めきれず迷走した感が強かったです。最近あまりAtCoderの問題を解いてなかったので（それ以外の問題を解いていた）、なんだか気持ちが入り切らなかったというのもあるかもです。
ABCでは3ヶ月ぶりの緑パフォを取ってしまいました。ちょっと詰まったら途端に思考が鈍るの改善していきたいですね…。
