Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 371

5完1WA

各問題

A - Jiro

場合分けを頑張りましょう(もっと簡単な解法あったりする?

出力する名前をミスって1WA...。

B - Taro

家ごとに長男が生まれたかどうかのフラグを持っておけばよいです。N<=100なので配列で十分です。(自分はmapでやった)

C - Make Isomorphic

頂点番号にとらわれず同型であればよいということなので、Gの頂点を next_premutation を使って全通りローテーションさせて問題を解けばよいです。

D - 1D Country

座標圧縮を頑張ってから累積和でクエリごとではO(1)になります。

E - I Hate Sigma Problems

より左側にある数字を優先するというルールにして、各数字が答えに寄与する回数を考えます。

A_i より左に同じ数字がなければ、(N - i + 1) * i 回の寄与があります。例えば N = 6, で i = 3 を考えると f(1, 3) から f(1, 6) の 4 つ、f(2, 3) から f(2, 6) の 4 つ, f(3, 3) から f(3, 6) までの 4 つが 3 回です。

A_i より左に同じ数字があるときは、それがなくなるまでは A_i は寄与できずなくなった後は常に寄与できるので、A_i の左で最も近い位置を j とすると (N - i + 1) * (i - j) 回の寄与があることになります。

F - Takahashi in Narrow Road

なんやねんこの崖は...

まとめ

水パフォでレート微増ですが水色には届かず。次回のABCで勝てないとその翌日のARCに出れなくなる背水の陣。