私の解法（ABC194_Cについて）

ブログ（アウトプット）を再開するためにこちらを書きます。今回は、2021年3月6日(土)に実施されたAtCoder Begginer Contest194のC問題について（C - Squared Error）*1、私の解法を解説します。

TL/DR

• 3行で表すと
  1. 素直（？）に実装するとTLEします
  2. 問題文の式を展開しよう
  3. 組み合わせは要領よく実装しよう
• 私の環境
  • WindowsでVSCode
  • WSL2を併用（Ubuntu 20.04.1 LTS）
  • C++ (GCC 9.2.1)
  • 私の提出: Submission #20720789 - AtCoder Beginner Contest 194

考え方

愚直な実装

Σの分だけ二重ループで解こうと思うと、次のようになると思います。

#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

*1:公式の解説はこちら: Editorial - AtCoder Beginner Contest 194

*2:参考：https://qiita.com/piroor/items/6300e665bc8ac314211b#%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%B9%E3%82%AF%E3%83%AA%E3%83%97%E3%83%88%E3%81%A7%E4%B9%B1%E6%95%B0