AtCoderのためのソースコード

1, AtCoderとは

おそらく少しプログラミングに詳しい方なら知っていらっしゃると思うのですが、与えられたinputに対して早く正確にoutputできるプログラムを世界中のユーザーより早くプログラミングする、といったソースコードを書く早さを競う競技プログラミングができるサービスになります。

先日こちらのサービスを知り、昨日のAtCoder Beginner Contest171に参加してみました。
参加してみて己の力不足、そしてこれまでどれだけusing UnityEngine;に頼っていたのかを痛感したのですが、そんなのはわざわざnoteにまとめるようなことではないので省略して、本題であるAtCoderで求められているソースコードと自分がこれまで書いていたソースコードについて書かせていただきます。

2, AtCoderで求められているソースコード

AtCoder Beginner Contest171に参加するにあたりその直前の大会であるAtCoder Beginner Contest170の問題も解いてみました。自分は時間内にA,B,Cの問題を解くことができましたが、Dの問題で行き詰りました。
ソースコード自体は恐らく正確に動いているのですが、どうやら自分のコードは実行時間制限を超過(TLE)しているようなのです。
それほど冗長なコードを書いているつもりはなかったのですが、解説を読んで納得しました。おそらくD問題の難易度設定は処理の簡略化も込みでの出題なのだろうなと思います。

自分はこれまで問題文をそのまま咀嚼し、処理の中で自然と得られる答えを出力するようなコードを書いていました。
しかし解説を見ると、一直線に与えられた答えを出すためだけのソースコードが求められているようでした。マシンにかける負担等を考えれば確かにそちらの方が正しいということがわかります。3で具体的なソースコードとともに詳しくお話していきたいと思います。

3, 自分の書いたコードと模範解答

ここでは実際にAtCoder Beginner Contest171にて出題されたD - Replacingという問題を例にとってお話ししたいと思います。(図1)

図1 D - Replacingの問いと制約

この問題を受けて自分は数列Aを配列aに格納し、クエリに応じて変化させてその都度和を出力すればよい、と考えて以下のコードを書きました。for文の中のCalcメソッド内にもう一つforがあり、二重でfor文ループを呼んでいることからも処理に時間がかかってしまうことがわかると思います。

解説を受けてコードを以下のように書き直しました。
この問題で求められているのは変化後の数列Aではなく、その和になります。そのためクエリによる和の変化量だけを求めて出力していくことでfor文を一個取り払うことができます。
数列Aを配列に保存することをやめ、代わりに数列Aの数字Anに応じて配列counts[n]をインクリメントし、countsの数字を入れ替えていくことでクエリに対応していく、といったコードになります。

4, 最後に

タイトルではAtCoderのためのソースコードなどと書きましたが、視点を変えることで処理にかかる時間を大幅に減らすという技術は普段の開発にも間違いなく役立ちます。

開発をしていると、例えば今回の例で言えば最初はsumだけが欲しかったのに数列Aが後から必要になってくる、ということが多く自分は脳死でfor文及びforeach文を使ってしまっていました。しかしモバイル向けの製品では特に無駄な部分にリソースを割きたくないので、今一度視点を変えて自分のコードを見直してみようと思います。

この記事で書いていることは、プログラミングを嗜むほとんどの方にとって当然のことなのだろうだと思います。しかし、独学でプログラミングをしていた自分には気付けなかった部分に気付けた良い機会だったのでnoteにまとめさせていただきました。