tatsumack blog

エンジニアによる雑記です

AtCoder Beginner Contest 102 振り返り

3回連続で400点問題を落として水色チャレンジに失敗していたので、今回は久々の4完でホッとした。

初めて600点問題でACできたので、解説記事でも書こうかと思ったけど、他の方の非常に分かりやすい記事があったのと、他の人の思考過程を知りたいと思うことがよくあるので、今回は自分が解答に至るまでの思考過程を記してみようと思う。

今回のABCの配点は100-200-300-600で、明らかにC速解き勝負だったので、なるべく早く解くことを意識した。

A - Multiple of 2 and N

パッと問題文を読んだときは2*Nを出力すれば良さそうだと思ったけど、サンプルを見て、Nが2で割り切れるときはNを出力すれば良いことに気づく。
Submission #2765392 - AtCoder Beginner Contest 102

B - Maximum Difference

問題文を読んだ時点で、配列要素の最大値と最小値の差を引く、という方針が浮かんだので、そのまま実装する。
Submission #2765973 - AtCoder Beginner Contest 102

C - Linear Approximation

問題文を読んだ時点では、方針が全く浮かんでこなかったので、「C速解き失敗」が脳裏をよぎる。

落ち着いて、問題を簡単に考えることはできないかと、式を眺める。
 A_i - (b+i) は、 B_i = A_i - i とすると  B_i - b として考えることができることに気付く。
よって、配列内の各要素からの距離の総和が最小となるような bを考えれば良くなり、少し単純になる。
まあそれでもまだ分からない。

簡単に考えるために、要素数が2のケースで考えてみる。すると、 bは2要素の間にあれば良いことに気付く。
次に、要素数が3のときを考えてみる。このとき、真ん中の要素と bが一致すれば良いことが分かる。

ということで、 bは配列の要素の中央値を選べば良さそう、という気配が濃厚になったので、実装してみる。
サンプルがすべて通ったので、ちょっと不安はありつつも、提出してみる。

ジャッジサーバーが詰まっていたのか、なかなかジャッジが走らなくてそわそわしたが、無事ACが出たので、一安心。
Submission #2767475 - AtCoder Beginner Contest 102

目標がC速解きだったのと、Dの600点問題は解けるわけないと思っていたので、ちょっと集中力を切らしてtwitterを眺めたりする。

D - Equal Cut

この時点で順位表を見ると、1位だったのでびっくりした。(スクショ取っておけば良かった)
Dも頑張って解いてみるかと思い直し、問題文を読み始める。

部分和を求める必要があるので累積和を使いそうだなーとは思ったが、方針は全く浮かんでこない。

簡単に考えるために、切り口を1つだとして考えてみる。
このときは、配列内のすべての切り口の位置を調べれば、 O(N)で簡単に切り口の位置を求めることができる。

ということで、「切り口1つの位置を考えれば良い」という状況にどうにかして落とし込めれば、この問題は解けそうだと思い始める。

ここで、切り口3つのうち真ん中の切り口を固定すると、左右の切り口の位置は切り口1つの問題に落とし込めることに気付く。「3つあるうち真ん中を固定すると、残りが決まる」というのはよくある形だったこともあり、気付くことができた。

無事にサンプルが通ったので提出するも、TLE。
Submission #2771181 - AtCoder Beginner Contest 102

計算量を落とせる場所がないか考えてみる。
真ん中の切り口の位置を更新するたびに、左右の切り口の位置を全探索して調べるのは無駄なことに気付く。

よくよく考えると、左右の切り口の位置は右にずれていくだけなので、真ん中の切り口を移動する際に、前回の左右の切り口の位置を覚えておいて、そこから計算すれば良さそう。(尺取法的なアプローチ)
Submission #2771925 - AtCoder Beginner Contest 102

サンプルが通ることを確認して、提出して、祈る。。
AC!初めて600点問題を通すことができた。

Dの提出直後は3位だったが、1WAだったこともあり、最終的な順位は4位だった。


振り返り

C問題もD問題も、パッと見よく分からないので、問題を簡単にして考えてみる、というアプローチが上手くいった。直近のコンテストで400点問題が解けないときは難しく考えすぎていたので、その反省が活かせたと思う。

次こそ水色!