C++でコードゴルフをする話

**こちらの記事は [競プロ Advent Calendar 2021](https://adventar.org/calendars/6713) の 5 日目の記事です。**
## 自己紹介
こんにちは、[まぐげんがー](https://twitter.com/gengar094kypro)といいます。中学3年生で、普段は競プロ（AtCoder<font color="ForestGreen">緑</font>）などをしています。
## 茶番

コードゴルフって楽しいですよね！提出欄のコード長順を押してっと…

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1021041/4b6b58dd-9ea5-1c2d-6923-c5f21ebcb074.png)

コラ～！

俺の読めない言語でコードゴルフするな～！怒りのあまり卓上調味料を全部倒してしまいました～！

読めないならしょうがないね。ではAtCoderへの提出率1位の言語　 **†C++†** でコードゴルフをしようじゃありませんか。

## コードゴルフをはじめよう

短くする問題は[ABC226D - Teleportation](https://atcoder.jp/contests/abc226/tasks/abc226_d)です。

まずは普通に解きましょう。gcdをとってsetに突っ込めばOKですね。

```cpp
#include<bits/stdc++.h>

int main()
{
	using namespace std;
	int n;
	cin >> n;
	vector<pair<int, int>> a_b(n);
	for(int i = 0; i < n; i++) cin >> a_b[i].first >> a_b[i].second;
	set<pair<int, int>> st{};
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		{
			if(i == j) continue;
			int x = a_b[i].first - a_b[j].first;
			int y = a_b[i].second - a_b[j].second;
			int g = std::gcd(abs(x), abs(y));
			st.insert(make_pair(x/g, y/g));
		}
	cout << st.size() << endl;
}
// 525byte 
```

ACしました！525byteです。もう少し考えると、傾きを計算してそれをsetに突っ込むのも正解になりそうなことがわかります。

```cpp
#include<bits/stdc++.h>

int main()
{
	using namespace std;
	int n;
	cin >> n;
	vector<double> a(n), b(n);
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	set<double> st{};
	for(int i = 0; i < n; i++)
		for(int j = 0; j < i; j++)
		{
			if(b[i] != b[j])st.insert((a[i] - a[j]) / (b[i] - b[j]));
			else st.insert(1<<30);
		}
	cout << st.size()*2 << endl;
}
// 358byte
```

もし`b[i]`と`b[j]`が同じだった場合には、めっちゃでかい数を入れることで`(x, y) => (x+0, y+1)`の魔法を表現しています。出力の時に、町から町への相互移動を可能にするための逆の操作（たとえば`(x, y) => (x+1, y-2)`だったら`(x, y) => (x-1, y+2)`のような）を数えるための`*2`をしています。

**200byteを切る**というのを目標にして短くしていきましょう。

### [AtCoder dos2unix UserScript](https://github.com/kmyk/atcoder-dos2unix-userscript)を入れる

これを入れることで改行文字をCRLFからLFにすることができます。これで(1 * 改行数)byte縮みます。

ちなみに僕は提出するときに毎回これを使っているので、上のコードのbyte数は改行を1byteとしてカウントしたものです。


### いらない改行、スペース、インデントを削る。変数は一文字で定義する。文法的に削れるところは削る。

> スペースを削る

比較的知られていないものだと、`vector<int> vec` の `<int>`の後のスペースは削ることができるというのがあります。

> 文法的に削れるところは削る

`#include`は`#import`と書けます（Objective-Cとの互換性を保つためらしいです）。

main関数の`int`と`return 0;`は省略できます。

あと、if文やfor文の後の`{}`は削れるところは削りましょう。

```cpp
#import<bits/stdc++.h>
main(){using namespace std;int n;cin>>n;vector<double>a(n),b(n);for(int i=0;i<n;i++)cin>>a[i]>>b[i];set<double>s;for(int i=0;i<n;i++)for(int j=0;j<i;j++)if(b[i]!=b[j])s.insert((a[i]-a[j])/(b[i]-b[j]));else s.insert(1<<30);cout<<s.size()*2<<endl;}
// 269byte
```

めちゃくちゃ見にくいですね。インデントをつけて表示しましょう。

```cpp
#import<bits/stdc++.h>
main(){
	using namespace std;
	int n;
	cin>>n;
	vector<double>a(n),b(n);
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];
	set<double>s;
	for(int i=0;i<n;i++)
		for(int j=0;j<i;j++)
			if(b[i]!=b[j])s.insert((a[i]-a[j])/(b[i]-b[j]));
			else s.insert(1<<30);
	cout<<s.size()*2<<endl;
}
// 269byte
```



削る前のコードに比べて100byte近く縮みました！！すごい！！

### 変数を一度に定義する

```cpp
#import<bits/stdc++.h>
int n,i,j;
main(){
	using namespace std;
	cin>>n;
	vector<double>a(n),b(n);
	for(;i<n;i++)cin>>a[i]>>b[i];
	set<double>s;
	for(i=0;i<n;i++)
		for(j=0;j<i;j++)
			if(b[i]!=b[j])s.insert((a[i]-a[j])/(b[i]-b[j]));
			else s.insert(1<<30);
	cout<<s.size()*2<<endl;
}
// 258byte
```

11byte縮みました。

### 脳死で`#include<bits/stdc++.h>`をしていないか確かめる

さて、このコードの中で使っているものでincludeしなければいけないものは

- `std::vector`
- `std::set`

- `std::cin, std::cout (std::endl)`

です。

`std::vector`は標準の配列に、`std::cin, std::cout`は`scanf, printf`に変えることでincludeするものが`std::set`だけでよくなります。

```cpp
#import<set>
int n,i,j,a[500],b[500];
main(){
	scanf("%d",&n);
	for(;i<n;i++)scanf("%d%d",&a[i],&b[i]);
	std::set<double>s;
	for(i=0;i<n;i++)
		for(j=0;j<i;j++)
			if(b[i]!=b[j])s.insert((a[i]-a[j])/(b[i]-b[j]));
			else s.insert(1<<30);
	printf("%d",s.size()*2);
}
// 242byte ?
```

AtCoderの最近の問題では改行を入れなくてもACになるので、`printf("%d\n", ...)`を`printf("%d", ...)`とかけます。

できました！提出してみましょう。

![unnamed.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1021041/c3c6fe23-8f89-eb22-d2e4-731dbd96c895.png)


うーん、WAが出てしまいました。`a[500]`と`b[500]`をint型で定義しているせいで、傾きが整数値になってきちんとした答えになってないことが原因です。ただ、これは`s.insert(...)`の中でdoubleにキャストして計算すればきちんとした答えが返ってきます。

double型にキャストするのは`(double)hoge`でもいいですが、`hoge*1.0`をするといい感じになります（浮動小数点数との掛け算の結果は浮動小数点数になるので）。`hoge*1.`と書いても動きます（C++では、`xxx.0`や`0.xxx`の`0`を省略できます）。

```cpp
#import<set>
int n,i,j,a[500],b[500];
main(){
	scanf("%d",&n);
	for(;i<n;i++)scanf("%d%d",&a[i],&b[i]);
	std::set<double>s;
	for(i=0;i<n;i++)
		for(j=0;j<i;j++)
			if(b[i]!=b[j])s.insert((a[i]-a[j])*1./(b[i]-b[j]));
			else s.insert(1<<30);
	printf("%d",s.size()*2);
}
// 245byte
```

![unnamed (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1021041/9c847626-ac49-043b-8a60-d6e4cade5a0a.png)


ACできました！

さっき言い忘れたのですが、グローバル変数はすべて0で初期化されているので、最初のfor文の`i=0`が削れます。

250byteを切りました。あともう少しです！

### for文、if文周りのテクを使う


```cpp
#import<set>
int n,i,j,a[500],b[500];
main(){
	std::set<double>s;
	for(scanf("%d",&n);~scanf("%d%d",&a[i],&b[i]);i++)
		for(j=0;j<i;j++)
			s.insert(b[i]-b[j]?(a[i]-a[j])*1./(b[i]-b[j]):1<<30);
	printf("%d",s.size()*2);
}
// 206byte
```

- `for(...; ~scanf(...); ...)`

知識ゲーです。[えびちゃんさん](https://rsk0315.hatenablog.com/entry/2020/05/09/170315#while-scanfd-n)の記事に詳しいです。

while文からfor文にすることで`for(...;`の部分に`scanf("%d",&n)`とかを入れられるようになって、1byte縮みます。

- `s.insert(b[i]-b[j]?(a[i]-a[j])*1./(b[i]-b[j]):1<<30)`

三項演算子です。`b[i]-b[j]`は`b[i]!=b[j]`と同じ意味です。（`b[i]`と`b[j]`が同じ時だけ結果が0,falseになります）

### 試行錯誤を重ねる・使えそうなテクを使う

```cpp
#import<set>
int n,i,j,a[9999],t;
main(){
	std::set<double>s;
	for(scanf("%d",&n);~scanf("%d%d",a+i,a+i+n);i++)
		for(j=i;j-->0;)
			s.insert((t=a[i+n]-a[j+n])?(a[i]-a[j])*1./t:n);
	printf("%d",s.size()*2);
}
// 193byte
```

- `for(j=i;j-->0;)`は`j--`が`j`を返すことを使って`j`を`i`から` 0`まで回しています。逆順にすると縮むパターンです。
- 配列を二つから一つにしました。`a[n]`と`b[0]`を対応させています。
- tという変数を追加して`a[i+n]-a[j+n]`を代入することで、`a[i+n]-a[j+n]`を複数回書かなくてよいようになっています。
- `scanf("%d%d",a+i,a+i+n)`は`scanf("%d%d",&a[i],&a[i+n])`と同じ意味です。直接ポインタを渡すと短くなります。

200byteを切れました！やったね！！




## うまくいかなかったもの

場合によっては上手くいきそうなテクニックなどです。

### 多重ループ凝縮

```
for(初期化1; 条件式1; 式1)
	for(初期化2; 条件式2; 式2b) 式2a
```

という式は

```
for(初期化1,初期化2; 条件式1;)
	条件式2 ? 式2a,式2b : (式1,初期化2);
```

と書けます。

202byteの時点でこれをすると[218byteになってしまった](https://atcoder.jp/contests/abc226/submissions/27615740)ので、そのあとは試していません。

### setの推論補助

`set<int> s{1}`を`set s{1}`と書けるやつです。

最初に入れる数をうまく調節すると[嘘解法が通ります](https://atcoder.jp/contests/abc226/submissions/27616291)。

これを使うと短くなる問題もあります（[これ](https://atcoder.jp/contests/abc217/submissions/25623475)とか）

## **追記**
[kyopro_friends](https://twitter.com/kyopro_friends)さんがさらに縮めてくれました！（ざっくり説明　iとjというポインタを持つことで短くなっています　すごい）

https://twitter.com/kyopro_friends/status/1472487708358750212

## 最後に

いかがだったでしょうか。C++でもけっこう短くできることがお分かりいただけたと思います。（ちなみにこの問題の全言語最短の記録はKotatsugameさんが書いたRakuの**60byte**（！！！）のコードです。すごい。）競技プログラミングをする時に役立つテクニックも結構あるので、まだコードゴルフをしたことがないという方は、C++でコードゴルフをしてみませんか？