みずくらげの競プロ記録

みずくらげです。競プロ始めました (2018. 01. 27)

青色になりました!

 

 
慣習に従ってやったことをまとめていこうと思います。ただ、前に変色してからもう一年以上経っていて、やったことが雑多かつ曖昧なので、ふわっと書くだけに留めておいて、せっかくなのでPythonからC++に転向した(今もがっつりPython使っていますが...)ことに触れてみます。
 

 

以下、水色なりたての頃との感覚的な比較です。
 
アルゴリズムに関して
元々新しいアルゴリズムを知るのは好きで、水色になった時点で蟻本の中級編までざっと読んでいたみたいです(水色になるまで)。現在は蟻本の上級編まで読んでいて(全ての問題を見たわけではないです)、最近週末に少しずつライブラリを増やしていっている段階です。ただ、上級編に載っているアルゴリズムやテクニックをコンテスト中で実際に使えた記憶はなく、せいぜい中級編に出てくる遅延評価セグメントツリーを貼るみたいなことしか活かせていない気がします。
 
実装力に関して
今もまだまだ遅くて、コンテスト中でも考察の時間よりも実装する時間の方が遥かに長いです。ただ、考察する段階である程度細部まで意識したり、実際にコーディングする前に全体像をイメージしてから書くということを意識するようになってから、徐々にスムーズに書けるようになっている気がします。
 
考察力について
ここが最近少し伸びた気がしていて、レーティングに直結している気がします。何というか、以前より思考を積み重ねることができるようになった気がしています(これまで深さ3までしか探索できなかったけど、4まで探索できるようになったようなイメージ?です。気がするだけかも知れません...)。月刊大学院生活は競技プログラミングの役に立つ!という記事が書けそう(書けません)。
また、これはこれからの自分によって否定されるかも知れないですが、無闇に紙を使って考察するのを意図的にやめたりしました(何だかサンプルを思考停止して触っている時間があると思ったので)。
 

 

PythonからC++転向への流れとそのお気持ち

はじめに

先に述べておきますが、別にPythonからC++転向を勧めている訳ではないです(お勧めしないという訳でもないです)。
自分はいわゆる生物系の人で、競プロを始める前に1年弱ほどPythonを趣味でほんの少しだけ触っていて、競プロを始める時も自然にPythonを使い始めたという流れです。C言語はもちろん、メモリとかアドレスとか全くわかりませんでした。プログラムは魔法で動いています。
 

きっかけ

Pythonで競プロを始めると困ることが2つある気がします。1つ目は速度の問題です。
 

 

 

注:これらはC++に手を出し始めて以降のツイートです(遡れなかった)。
 
僕が始めた頃は、Pythonで上に行くのは厳しいみたいな風潮が主流だった気がします。当時、C++に移行した方がいいのかなぁみたいな漠然とした意識は持っていたと思います。
 
ただ、この問題は高速化のテクニックをある程度身につけてしまうと、本当にTLEで通らなかったケースはほとんどなかった気がします(上のようにうっかり忘れてしまう時はありますが)。実際、maspyさんによって、この記事執筆時点までのratedコンテストで、難易度2800以下のものが全てPython / PyPyでACできることが言及されています。この事実は僕を含むPython勢にとってまさに希望の光でした。
 
もし適切なアルゴリズムを使っているのにTLEになってしまう...という方は
じゅっぴーさんの記事が参考になると思います。特にPyPyの存在を知らない方は、ぜひ使ってみてください。Pythonのコードがそのまま使えます。(自分は競プロを始めてから数ヶ月間ほどPyPyを知らずに過ごしていてTLEに苦しんでいた気がします...)。
 
2つ目は、アルゴリズム入門として初心者にお勧めされる螺旋本も、競プロer必携の蟻本も、ネット上の解説記事の大部分もC++で書かれている(要出典)ことです。当時の僕はどうしていたかというと、螺旋本を使っていた時はAOJ上の提出コードの中から読みやすいものを探って、理解したり見よう見まねでコードを書いたりしていました。解説記事は後ろにpythonって付けてググっていた気がします。不便ですね。しばらくして意外と読めるのでは?と思ってからは、C++のコードを睨んで理解するということをしていました。ということをしていると、きちんと勉強したり書きたい欲も出てきます。
 
まとめると、
1. いつか解けない問題が現れるのならC++勉強しておいた方がいいのでは?
2. どうせC++読むなら、ちゃんと勉強したり自分で書いてみたい。
という理由でC++始めました。
 
 
 

1年ちょっとC++を触ってみた感想

メリット
  • C++のコードが正確に読める
それはそうなんですが、この部分は大きいです。諸々の解説記事だったり、解説放送の実装だったり、蟻本だったりはC++で書かれていることが多いので、それを実際にコードを見て理解できるという面は強いです。ライブラリもC++で落ちていることが多く、自分で作る際にとても参考になったりします。(何だったらそのまま使うこともできます。)
 
  • 速い
速いです。ただ、実感としてはこの恩恵はあまり受けてない気がします。実際コンテスト中に、「この問題はPython (PyPy)だと遅くて通らなさそうだからC++で書こう」みたいな気持ちになったことはほとんどない気がします。
 
デメリット
  • ライブラリの整備が大変
一般に言語の乗り換えで起きる問題だと思います。特に、自分のようにPythonC++を併用する場合は、ライブラリを2つ用意するみたいな羽目になります。(実をいうと、蟻本の中級編以降はC++のライブラリしか整備していないので、高難易度の問題はC++で解くみたいなことになっちゃってます。今はこのスタンスもそこまで問題視していないですが、C++に慣れるまでは、そのアルゴリズムがコンテストででたらC++で書く必要があって、バグを生んで悲しくなるみたいなことはありました。)
 
  • 学習コストが高い
Pythonは雰囲気でかけますが(というと怒られそう)、C++は比較的気を使うことが多く、必要となる前提知識も比較的多い気がします。慣れないうちはバグを量産して時間が溶けます。悲しい。コンテスト中でバグが発生してしまうとレートが溶けてさらに悲しくなります。
 
  • コーディング量が多い
一般にPythonに比べて書く量が多くなります。今でもPythonをよく使っているのはこれが理由だったりします。ただ、最近は慣れだったり適宜マクロを使ったりしているからか、そこまで負担は変わらなくなってきているような気もします。
 
 
これぐらいでしょうか?結局どうするべきかはよく分かりません。C++に興味があれば触ってみてもいいのでは?ぐらいしか言えません。
 
 
 

ちょっと触ってみたい人が知っておくと良さそうなこと(あくまで競プロのためのC++です)

もしPythonからC++に乗り換えたい!という人がいた時のためにオススメだったり自分がつまづいたポイントを載せておきます。あくまで現状の自分目線なので微妙かも知れませんが、、、
 
  • 環境構築
自分が始めるときは結構苦労した気がするのですが、最近はこの手の記事は調べたところ充実してそうな気もしました。自分はmacですが、最近この記事に従って新しいPCに構築し直しました。code runner便利ですね!(最近まで手打ちでコンパイルしていた...)
#include <bits/stdc++.h>(ライブラリをまとめて一行でincludeする)なら、macに元々入っているclangではなくgccを使う必要があります(自分は使っていませんが)
 
自分が始めた時は1章までしかなかったですが、増えていますね!やっぱり最初は触って慣れるのが良さそうです。
 
ライブラリの使い方などお世話になります。日本語版もあります。
 
令和ABCの解説動画では実装パートもあり、話しながらコーディングしてくれるので、実装のお気持ちがわかったりすることもあってオススメです。
 
慣れてきたら、C++の巷の書籍をざっと読んでみるのも理解が進んで良さそうです。
 
  • %について
ここで殊更とりあげるのはちょっと変ですが、実際自分が一番大変で記憶に残っているのはこれです。
負の数に対してだけ、PythonC++で挙動が違います。Pythonだと -7 % 5 = 3 ですが、C++の場合、-7 % 5 = -2 となります。同一の演算子で挙動が異なるのは怖いですね。
 
 

 

終わりに

青色、嬉しいんですが、今年の目標は1800なんですよね...厳しい。
 
(:]ミ(:]彡(:]ミ(:] 彡