【競プロ】Pythonを使おう

この記事は新歓ブログリレー2024 24日目の記事です。

23BのNzt3です。
普段はAtCoderで競技プログラミングをやったり、CTFで競技プログラミングをやったりしています。

みなさまも競技プログラミングをやりましょうね。

競プロでの言語選択

この記事を読んでいるみなさんは当然競技プログラミングをやっていると思うのですが、どの言語を使っていますか？

AtCoder ProblemsにユーザーIDを入れるとそのユーザーの各言語でのAC数を見ることができます。
私のAC数は次の画像の通りです。
languages

C++ 2237AC
プロデル 53AC
Python 13AC

C++を使っていることがわかりますね。
~~え、13ACで「Pythonを使おう」なんて記事書いてるんですか！？~~

速い言語を使おう！

競プロでは実行時間が大事

競技プログラミングは「実行時間制限内に正しい答えを出力するプログラム」を提出すれば勝ちです。アルゴリズムの時間計算量を削減しなくとも、実行時間が削減できれば良いです。
計算量のオーダーが削減できたとしても、定数倍の問題で実行時間が悪化することもあります。

基本操作が高速な言語は有利

同じようなコードを書いても言語によって実行時間には差があります。コンパイル時の最適化によりそもそも書いた通りには動いていないこともありますが、書いた通りに動いたとしても速度には差が生まれます。

競プロではこの速度の差がACとTLEを分けることがあります。

ABC330F - Minimize Bounding Squareを考えてみましょう。
この問題は $O (N)$ の貪欲法が想定解ですが、貪欲法の正当性を示すことは結構難しいです。より正当性が示しやすい解法に二分探索による $Θ (N (lo g N + lo g M))$ 解法があります。この解法の一部の実装をサボると $Θ (N lo g N lo g M)$ になります。C++を使えば適当に実装しても実行時間は1800ms程度になりACを得ることができます。

Pythonは基本動作があまり速くない言語です。遅いというほどではないですが、高速な言語で通る非想定解法の中にはPythonでは通せないものもあります。

Pythonを使おう！

この章の対象読者は「すでにC++を使って競技プログラミングを進めている人」です。これから競技プログラミングを始めるという人は
Pythonで競技プログラミングの勧め【AdC2019 38日目】を読むか、C++を使ってください。

C++で起きるミス

ABC327B - A^A

整数 $B$ が与えられます。

$A^{A} = B$ であるような正の整数 $A$ が存在するならばその値を、存在しないならば -1 を出力してください。

$1 \leq B \leq 1 0^{18}$

これを解きます。
$A$ が小さくとも $A^{A}$ は非常に大きな値になります。 $A$ を1から順に全探索して、 $A^{A} \geq B$ を満たす最小の $A$ を探しましょう。

long long B,A=1;
cin>>B;
while(pow(A,A)<B){
  A+=1;
}
if(pow(A,A)==B){
  cout<<A<<'\n';
}else{
  cout<<"-1\n";
}

おっと、これはWAのコードですね。std::powは浮動小数点数が返ってくるのでこれでは入力が $1 5^{15} + 1$ のようなときに誤判定してしまいます。
適切に整数の冪乗を定義しておきましょう。

long long ipow(long long A,int n){
  long long ret=1;
  for(int i=0;i<n;i++){
    ret*=A;
  }
  return ret;
}

long long B,A=1;
  cin>>B;
  while(ipow(A,A)<B){
    A+=1;
  }
  cerr<<A<<endl;
  if(ipow(A,A)==B){
    cout<<A<<'\n';
  }else{
    cout<<"-1\n";
  }

これでOKですね。手元でもちゃんと動くし、ACも出ました。

実はやばいです。 このコードは $B > 1 5^{15}$ のケースで符号付き整数のオーバーフローが発生します。
今回の問題はいろいろなことが噛み合ってACが出ていますが、やばいコードです。
19^19=6353754964178307979 (mod 2^63)
こういうミスを防ぐためにもコンパイルオプションやデバッガの設定をしっかりと行いましょう。

Pythonで起きないミス

整数をたくさん掛けてもオーバーフローしない言語が欲しいですね。あと整数の累乗が簡単にできると嬉しいです。
具体的にはこんなコードでACが得られるような…

B=int(input())
ans=1
while ans**ans<B:
  ans+=1
if ans**ans == B:
  print(ans)
else:
  print(-1)

Pythonですね。

C++だと

std::powは浮動小数点数を返す
$1 6^{16}$ はlong longにもunsigned long longにも収まらない

ということを考えなければいけませんでしたが、Pythonならその必要はありません。
さまざまな罠を無視して問題の本質だけを考えることができます。
記述も短いので書く時間も短縮できて嬉しいですね。

~~PythonにはPython特有の言語の罠があるらしいですが、私はPython使いではないので気にしません。~~

Pythonで非想定解を通そう

Pythonは普通に整数の演算を書くだけでいい感じに多倍長整数を使ってくれる上にそこそこ速いので、難しめの問題を適当に書いて通すことができます。

私がコンテスト中にPythonを使って通した非想定解を紹介します。

ABC339F - Product Equality

$N$ 個の整数 $A_{1}, A_{2}, \dots, A_{N}$ が与えられます。

以下の条件を満たす整数の組 $(i, j, k)$ の個数を求めてください。

$1 \leq i, j, k \leq N$

$A_{i} \times A_{j} = A_{k}$

制約

$1 \leq N \leq 1000$

$1 \leq A_{i} \leq 1 0^{1000}$

これは愚直に $i, j, k$ を探索すると $Θ (N^{3})$ になりますが、事前に $A_{i}$ の値ごとに数を数えてdictなどに記録しておけば $i, j$ の探索だけにできて $Θ (N^{2})$ にできるやつですね。

この程度で通るならF問題にはなってないと思いますが、まあ多少枝刈りを入れておきましょうか。
通りました。(462ms)

Good Bye 2023D - Mathematical Problem

奇数 $n$ が与えられます。
leading zero無しで $n$ 桁の平方数 $n$ 個を構築してください。
ただし、それらの数に使われる数字は多重集合として一致している必要があります。

$1 \leq n \leq 99$

結構難しそうですね。今回は $n$ の小ささを利用して解を埋め込んでみましょう。

Pythonで適当な探索を書くと、1分ほどで全ての入力に対する解を構築できました。
あとはこれを埋め込んでC++で提出すればACが得られます。

想定解では特殊な平方数を用意することで再帰的に多くの平方数を構築していましたが、埋め込んでしまえばそのようなことを一切考えずに問題を解くことができました。

Pythonを使うことで考察段階をスキップしてACを得ることができましたね。

ICPCでもPythonを使おう

ICPCで使える言語(2023 国内予選)

競技参加者が使用できるプログラミング言語は C, C++, Java, Kotlin, Python3 のみです。

例えばBoost, NumPy, AC Library は言語で標準で提供されているライブラリではないので利用できません。

ICPCでもPythonが使えますね。

ICPC国内予選はテストケースを手元のPCで処理し、出力結果を提出します。実質的に実行時間制限が3時間(競技時間全体)なので、PythonがC++より多少遅い程度で問題になることはありません。

ICPCのペナルティのルールもPythonを有利にします。序盤の問題を通すのにかかった時間が後半の問題のペナルティにも加算されるため、序盤の速さが非常に重要なルールです。上位を狙うには簡単な問題をミスなく高速に通すことが必要ですが、これは記述が短く多倍長整数が強いPythonの得意分野です。

~~私はC++を使う方が早くてミスがないのでC++を使います。~~

終わりに

競プロで使うC++は強いですが、競プロで使うPythonも強いです。みなさまもPythonを使えるようになって手札に「やたら速い多倍長整数で殴る」を加えて非想定解を通しまくりましょう。

明日の担当は@cp20さん,@synoriさん,@nosaercさんです。お楽しみに。