こちらの記事は 競プロ Advent Calendar 2021 の 5 日目の記事です。
自己紹介
こんにちは、まぐげんがーといいます。中学3年生で、普段は競プロ（AtCoder緑）などをしています。
茶番
コードゴルフって楽しいですよね！提出欄のコード長順を押してっと…
コラ～！
俺の読めない言語でコードゴルフするな～！怒りのあまり卓上調味料を全部倒してしまいました～！
読めないならしょうがないね。ではAtCoderへの提出率1位の言語 †C++† でコードゴルフをしようじゃありませんか。
コードゴルフをはじめよう
短くする問題はABC226D - Teleportationです。
まずは普通に解きましょう。gcdをとってsetに突っ込めばOKですね。
#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に突っ込むのも正解になりそうなことがわかります。
#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を入れる
これを入れることで改行文字をCRLFからLFにすることができます。これで(1 * 改行数)byte縮みます。
ちなみに僕は提出するときに毎回これを使っているので、上のコードのbyte数は改行を1byteとしてカウントしたものです。
いらない改行、スペース、インデントを削る。変数は一文字で定義する。文法的に削れるところは削る。
スペースを削る
比較的知られていないものだと、vector<int> vec の <int>の後のスペースは削ることができるというのがあります。
文法的に削れるところは削る
#includeは#importと書けます（Objective-Cとの互換性を保つためらしいです）。
main関数のintとreturn 0;は省略できます。
あと、if文やfor文の後の{}は削れるところは削りましょう。
#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
めちゃくちゃ見にくいですね。インデントをつけて表示しましょう。
#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近く縮みました！！すごい！！
変数を一度に定義する
#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だけでよくなります。
#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", ...)とかけます。
できました！提出してみましょう。
うーん、WAが出てしまいました。a[500]とb[500]をint型で定義しているせいで、傾きが整数値になってきちんとした答えになってないことが原因です。ただ、これはs.insert(...)の中でdoubleにキャストして計算すればきちんとした答えが返ってきます。
double型にキャストするのは(double)hogeでもいいですが、hoge*1.0をするといい感じになります（浮動小数点数との掛け算の結果は浮動小数点数になるので）。hoge*1.と書いても動きます（C++では、xxx.0や0.xxxの0を省略できます）。
#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
ACできました！
さっき言い忘れたのですが、グローバル変数はすべて0で初期化されているので、最初のfor文のi=0が削れます。
250byteを切りました。あともう少しです！
for文、if文周りのテクを使う
#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(...); ...)
知識ゲーです。えびちゃんさんの記事に詳しいです。
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になります）
試行錯誤を重ねる・使えそうなテクを使う
#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になってしまったので、そのあとは試していません。
setの推論補助
set<int> s{1}をset s{1}と書けるやつです。
最初に入れる数をうまく調節すると嘘解法が通ります。
これを使うと短くなる問題もあります（これとか）
追記
kyopro_friendsさんがさらに縮めてくれました！（ざっくり説明 iとjというポインタを持つことで短くなっています すごい）
最後に
いかがだったでしょうか。C++でもけっこう短くできることがお分かりいただけたと思います。（ちなみにこの問題の全言語最短の記録はKotatsugameさんが書いたRakuの60byte（！！！）のコードです。すごい。）競技プログラミングをする時に役立つテクニックも結構あるので、まだコードゴルフをしたことがないという方は、C++でコードゴルフをしてみませんか？