大学院生がFortranでAtCoderをやってる感想

対象読者

Fortran知ってるけどAtCoderやってない人
FortranでAtCoderというパワーワードに惹かれた方

研究者がAtCoder始める時の勘違いあるある(ないない)

AtCoderは様々な計算機科学手法が出てくる
アルゴリズム特化です。分子動力学法や流体シミュレーションなんか出てくる気配は今の所ありません。

実行時間が短いコードの勝ち
違います。出題された問題を制限時間内に多く解いて点数をたくさん稼いだ人が勝ちます。同じ点数の人同士は速く提出したほうが上になります。

定数倍高速化を学べる
直接的には学べません。アルゴリズム最適化が高速化の主な手段です。間接的には学べます。自分でライブラリを作成する際に、たまにこだわる。多次元配列に添字順でアクセスする的な話は学べます。

複素数型で周りと差をつける
AtCoderでは複素数型を表立って使うことはありません。二次元座標の表現をするときに、好みで利用したい人はしてください。

実行ファイルを提出する
ソースコードを提出します。コンパイルはAtCoder側で勝手に行われます。gfortran -O2 -o ./a.out ./Main.f08でコンパイルされるそうです。

MKL/並列化/SIMD化で回りと差をつける
上記の理由からコンパイルオプションが指定されているので、できない or 限定的です。

アルゴリズムが研究で役に立つ
研究にも役立つアルゴリズムってそんなに数ありません。

• FFTの畳み込み、相関関数
• 累積和
• 二分探索
• セグ木

あたりでしょうか。
個人的にはアルゴリズムよりも「思いついたロジックをびゃーっとコード化する」という部分の旨味が大きいと感じています。

Fortran使用者から見たAtCoderの問題

ABC(AtCoder Begginer Contest)は、週に一回くらいのペースで休日の夜9時から行われるコンテストです。A問題~F問題の計6問が出題されます。
各問題をFortranで解くために必要な要素は大体こんな感じです。

A問題

• 簡単な入出力を行える
• 簡単なif文が使える
• 各変数を正しく宣言出来る
• 演算子(+,-,/,*など)を正しく扱える
• 代入処理を行える
• （簡単でいいので）ゼロから完成したコードを書き上げられる

感想: Fortranは標準入出力の制御がAtCoder向けなので、詰まりどころは少ないです。

B問題

• 固定配列or動的配列を正しく宣言、使用できる
• やや複雑な入力を受け取れる
• 簡単なdoループ、do whileループを扱える
• 簡単な計算をコードに落とし込める
• 真偽、かつまたは、などをコードに落とし込める
• 競技プログラミング独特な問題文に慣れる

感想: 簡単なロジックを思いついてコードで表現するという練習ができると思います。

C問題

• 計算量の概念を理解し、自分の解法が制限時間内に終わるか予測できる
• 計算量を減らす必要がある場合、減らせる
• メモリ使用量についても理解し、減らす必要がある場合減らせる。
• 簡単なアルゴリズムを使える
• $O(N log N)$ソートを自作する
• デバッグができる
• if,do,do while,配列,真偽値などを複合して使用できる
• よく使う標準組み込み関数をぱっと書ける(max(), maxval(), sum()など)
• 簡単なライブラリを作れる

感想: Bよりちょっと複雑なロジックになります。高校レベルの数学がたまに出ますが、計算自体は簡単なことが多いです。ほかの言語より苦労することが多くなってきます。

D以降

• ビット演算が出来る
• 使えるアルゴリズムを増やす
• 抽象的なライブラリが作れる
• moduleを書ける
• OOPを学ぶ

感想: ライブラリ整理などは必須なので、自作moduleの作成などの練習になると思います。

C問題まで解けるようになった人の進路

Cまで解けている人々は、Fortranの基礎文法を使える、Fortranのコードをイチから書ける、などの能力は備わっていると思います。そういう人たちは以下の進路があるでしょう。

• 言語を変えてAtCoderをやる(いい趣味をもったね)
• AtCoder卒業。研究でバリバリコードを書いて論文を書く(最短距離で実績を積めるね)
• FortranでAtCoderを続ける(祝Fortran教入信)

上2つをおすすめします。Fortranは競技プログラミングの難しい問題を解くのにはあまり向いていません。研究に活かせる知識の割合も段々減ってきます。

筆者は、Fortranに取り憑かれてしまったため、FortranでAtCoderを続けています。(がんばります)
会社というものに入社したのでGoでやっていきます。

FortranでAtCoderをやると見えてくるFortranの良いところ悪いところ

似た視点の記事

良いところ

序盤の学習コストが低い
A~Cくらいまでの問題に関してなら、C++よりも学習コスト低めだと思います。

見やすい書きやすい
配列演算子は書きやすいです。最近だとelemental functionなんかも良いです。入力の受け取りはpythonより簡単です。

はやい
はやいです。ですが、実行時間を見るとC++やRustに負けているような感じがします。本当に早いのか? JuliaはAtCoderでは不遇の時代を過ごしていますね。元気ですか?

OOPが出来る
自作ライブラリがOOPによってサマになるので良いです。演算子のオーバーロードもできます。関数ポインタもあります。

道なき道を進める
人と違う道を歩みたいそこのあなた、ぜひFortranを。
AtCoder Problemsとか見るとわかりますが、Language Ownerとかも難易度低めです。

研究に昇華還元できる
研究でFortranを使っている場合、コーディングスピードが単純に早くなるため良いです。研究室内の既存コードの書き方が気に食わなくなってきて、リファクタリング衝動に駆られるという副作用があります。

悪いところ

データ構造が貧弱
vector, linkedlist, dict, set, queue, stack, deque, heapなどがありません。自分で実装するか、他の人が作ったライブラリを拝借する必要があります。ソートする関数もありません。

テンプレート・ジェネリクスがない
正直データ構造が貧弱なのは別に構いません。どうせBITやsegment treeなんかは誰でも自作する必要があるんですから(ACLからそっと目をそらす)。しかしテンプレート・ジェネリクスがないのは痛いです。例えばvectorを作成すると、

• vector_int32_mod
• vector_int64_mod
• vector_character_1000_mod
• vector_vector_int32_mod
• ...

と型の数だけ構造型を作成しなければなりません。型パラメタがありますが、根本的な解決にはなりません。
また、マクロに関しては、コンパイル時にオプションでいろいろやるヤツと、fortran2008の規格のとの2つがあるのですが、どちらもAtCoderの環境では使用できません。この前抽象化遅延評価セグメントツリーを作成しましたがとても大変な思いをしました。しかしその分Fortranへの愛が強まりました(ﾄｩﾝｸ)。

構造体の要素にアクセスするのに%を使う
「見やすい」という大切な特徴が台無しになってしまう。いやああああああ。普通にキモくないですか。
Goを学んで気づきましたが、無駄にOOPするよりも手続き型で頑張るほうがまだ自然かもしれないです。

情報が少ない、散らばっている
これも地味に痛いです。知らない関数とかもまだ普通にあり、最近はmaxloc,minloc,pack,merge,move_allocなどを学びました。

学習コストが高い
以上の理由から、D以上の問題を安定して解くためには自作でライブラリが必須になります。しかしFortranでライブラリを作成し始めると途端に時間が溶けていきます。特に型に対して抽象的なものを作ろうとすると工夫が必要になります。pythonやC++のことが途端に羨ましく思えてきます。

書き方が多様
Fortranで競技プログラミングをやっている皆さんは紳士淑女が多いため、大体implicit noneを使用しています。わたしはimplicit noneに加えてuse,intrinsic :: iso_fortran_envも書き加えて紳士度を上昇させています。一方暗黙の型宣言を最大限に活用する手もあるように思えます(競プロする場合に限る)。最近はシンタックスハイライトなども効いてくるため、昔ほど忌み嫌われる存在ではないような気もします。

まとめ

Fortranでプログラミングをすると、研究室内で唯一無二の存在になれる。