Help us understand the problem. What is going on with this article?

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

対象読者

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

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

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

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

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

並列化すると有利
できません。

SIMD化で高速化
出来ません。

複素数型で周りと差をつける
AtCoderでは複素数型は出てきません(たぶん)。浮動小数点でさえ、頻繁には出てきません。

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

MKLで爆速コードを書けば最強じゃね?
上記の理由からコンパイルオプションが指定されておりMKLは使用できません。

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

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

あたりでしょうか。
個人的にはアルゴリズムよりも、「コードを書く経験が積める」という部分の旨味が大きいと感じています。

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

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

A問題

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

B問題

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

C問題

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

D以降

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

A~B問題に関しては、大体他の言語と同じくらいの難易度です。(文字列・文字列型の入力、処理がちょっと大変)
C以降の問題では他の言語より苦労することが徐々に多くなって来る印象です。

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

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

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

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

筆者は、Fortranに取り憑かれてしまったため、FortranでAtCoderを続けています。(がんばります)

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

https://qiita.com/B3LYP/items/86711580450af1715a5b

似た視点の記事

良いところ

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

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

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

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

道なき道を進める
人と違う道を歩みたいそこのあなた、ぜひFortranを。

研究に昇華還元できる
研究で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への愛が強まりました(トゥンク)。

構造体の要素にアクセスするのに%を使う
「見やすい」という大切な特徴が台無しになってしまう。いやああああああ。普通にキモくないですか。

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

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

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

その他

最初はAtCoderで使えるFortranの便利な表現Tipとかを書くつもりでした。別の記事に書きます。

Authns
python fortran atcoder緑 ゲーム作成 分子動力学法
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away