【AtCoder】 また負けてるABC362

　どうも駆け出しRustaceanの緑抄と申します。水落ちの圧に苛まれていたらDPにぶつかって玉砕しました。一応振り返りだけしておこうと思います。

A問題-Buy a Pen

A - Buy a Pen

　とりあえず嫌いでないものをそのまま比較するように書けばokです。
実装例

B問題-Right Triangle

B - Right Triangle

　3つの直線のうち二つをとってそれらが直角かを判定してあげればいいです。直角ならば傾きの積が-1になります。なのでx座標、y座標の差をとって傾きを調べればokです。…とつぜんこれやれと言われると焦りますね。
実装例

C問題-Sum = 0

C - Sum = 0

　突然にちょっとすぐには思い浮かばない問題が飛び出してきました。ここで焦ったのがよくなかったですね。少し考えれば最小を取り続けたものが0以下で最大を取り続けたものが0以上であれば確実に0にできます。ではどう復元するかといえば最大のものか最小のものをとり続けて最小の場合か最大の場合になったらあとはその限界の場合を辿るとかでできます。この実装に手間取りまくってしまいました。全体としてバグのないコードを書くのが遅いというのがかなりのネックになっているのが課題ですね。
実装例

D問題-Shortest Path 3

D - Shortest Path 3

　落ち着いて問題文を読みましょう(n敗)。頂点と辺の重みの和を距離とするとは言っていますが同じ頂点に2回以上入ることは最短の場合あり得ないのでその頂点に入る時に一緒に頂点の重みも足すと考えて差し支えないので結局は始点から各頂点への最短経路を計算する問題に帰着されます。はい、いつものダイクストラ法です。計算量は$${O(NlogN)}$$です。詳しい解説は他の記事に譲りますが簡単にいうと始点から一番近い頂点を取って周囲の最短距離を更新して最短の選んでない頂点を選んで…を繰り返すアルゴリズムです。
実装例

E問題-Count Arithmetic Subsequences

E - Count Arithmetic Subsequences

　解けなくて終わり…水コーダーは解けないといけない問題でした。等差数列は$${a_{n}=a(n-1)+b}$$と表されるからHashMapでaとb持つのか？！とかやってましたが今回$${N\leq80}$$なので別に$${O(N^{4})}$$くらいまで許容なんですよね。1の場合は答えが明らかに$${N}$$なので$${N\geq2}$$の場合を考えればよく、そうすると二つの数字を添え字に持つことで等差数列を表現できます。そして最後に何項目かの添え字をもてば計算できそうです。初項なら最初の項に1足して、2以上なら等差数列上で次の二つの組みが計算できるので後ろにあるその組みに当たる計算結果を足す形にすることでうまく動的計画法で$${O(N^{4})}$$で計算できます。DPに項の値を直で持っても添え字を持っても計算できます。
実装例

　やはりコーディング速度と典型の対応力が未だ不足していて厳しいですね。もっと精進します。