ブログ（アウトプット）を再開するためにこちらを書きます。今回は、2021年3月6日(土)に実施されたAtCoder Begginer Contest194のC問題について（C - Squared Error）*1、私の解法を解説します。
TL/DR
- 3行で表すと
- 素直（？）に実装するとTLEします
- 問題文の式を展開しよう
- 組み合わせは要領よく実装しよう
- 私の環境
考え方
愚直な実装
Σの分だけ二重ループで解こうと思うと、次のようになると思います。
#include
#define ll long long
using namespace std;
int main() {
ll N, ret = 0; cin >> N;
vector A(N+1); // 0オリジン（始まり）なので+1しています
for (int i = 1; i <= N; i++) cin >> A[i];
for (int i = 2; i <= N; i++) {
for (int j = 1; j <= i - 1; j++) {
ret += (A[i] - A[j]) * (A[i] - A[j]);
}
}
cout << ret << endl;
return 0;
}
しかし、これでは、入力例は問題なくても、次で詳細を説明するTLEが起こりそうな量の入力には耐えられません。
入力例1
$ IN=1.in; cat $IN; timeout -sKILL 2 bash -c "time ./a.out < $IN"
3 // 入力
2 8 4
56 // 出力
real 0m0.017s // 計算時間
user 0m0.001s
sys 0m0.005s
入力例2
$ IN=2.in; cat $IN; timeout -sKILL 2 bash -c "time ./a.out < $IN"
5
-5 8 9 -4 -3
950
real 0m0.017s
user 0m0.000s
sys 0m0.006s
最大の入力例
$ IN=stdin.; head $IN; timeout -sKILL 2 bash -c "time ./a.out < $IN"
300000
18
72
-144
3
10
-57
94
106
149
Killed // TLE
私の解法
N=3で式を眺めてみます。簡単のためAiをabcと表すことにします。
同様にN=5で式を眺めてみますと、次のようになります。
ここで、それぞれの項の特徴に気が付きます。
- ２乗の項
- ①自身以外の項との組み合わせの数だけ項が存在する：N-1個
- 各項の積
- ②aからeの入った袋から2つ球を取り出すときの組み合わせの数
②に関して、安直に組み合わせを考えると、次のようにTLEを起こしそうです。
ですので、計算方法でカバーします。第２項だけに着目すると次のように計算量を少なくできそうです。
これが私の実装の解説となります。変数名などが今一つですが、コード長は423 Byte、実行時間63 ms、メモリ5480 KBと、そこそこの実装だと思います。
テスト（タイムアウトをしないか試験する）
ABCのC問題は愚直に計算するとTLEが起きる問題が多いと思うので、ローカル環境でも、TLE が起きそうなケースを試しておくとよいと思います。
コマンドの準備（汎用的）
Linuxのコマンドにタイムアウトというものがあります。
$ timeout --version
timeout (GNU coreutils) 8.30
タイムアウトさせたい時間とその時のシグナルを設定できます。
# timeout -sKILL 2 ./a.out < stdin
また、実行時間も計測したいので、timeコマンドも挟んでみましょう。
$ timeout -sKILL 2 bash -c "time sleep 1"
real 0m1.003s
user 0m0.001s
sys 0m0.001s
sleep（実行時間を想定）がtimeoutを超えると次のようになります。
$ timeout -sKILL 2 bash -c "time sleep 3"
Killed
今回のテストデータの準備
試験本番ではテストデータの用意の仕方間違えました…。
$ echo 300000 > stdin; for i in `seq 1 300000`; do echo $i >> stdin; done
$ head stdin
300000
1
2
3
...
これでは制約事項「@|Ai|<=200@」が満たされていませんね。実際に入力してみると桁あふれしていることが分かります。
$ ./a.out < stdin
-7529530734753409792
ですが、実行時間だけを取ってみれば、間に合っていることが分かります。私はこの段階で、提出をしました（汗）。
$ timeout -sKILL 2 bash -c "time ./a.out < stdin"
-7529530734753409792
real 0m1.072s
user 0m0.236s
sys 0m0.079s
本来であれば、絶対値が200以下の自然数ですので、次のように与えるべきですね*2。そして、これでは完全なランダムではないですが一旦置いておくことにします。10秒ほどで、テストデータが作成できました（答えは不明です…）。
$ time (echo 300000; while true; do echo $(( ($RANDOM - 16383) % 200 )); done) | head -n 300001 > stdin
real 0m9.753s
user 0m7.171s
sys 0m10.019s
$ head stdin.
300000
18
72
-144
3
10
-57
94
106
149
実際に実行してみると、次のようになりました。1秒以内に結果が出力されているので問題なさそうですね。
$ wc -l stdin; timeout -sKILL 2 bash -c "time ./a.out < stdin"
300001 stdin
1187018545951196
real 0m0.701s
user 0m0.190s
sys 0m0.036s
蛇足
記事書くの大変ですね。この文章で5,000文字くらい（原稿用紙12枚、35ツイート分）で、2,3時間くらいかけました。丁寧な解説をされている先輩方には頭が上がりません。また、感想戦？組の実装は驚異的です。bashやawkでの実装までありました。もはや脱帽というか、禿げそうです！それは脱毛w
