Fortran vs AtCoder 〜青色になったよ〜

# ようやくFortranでAtCoder青になれました!

先日のABC374(2024/10/05(土))でようやく青色になれました!

![Screenshot from 2024-10-21 23-49-42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2296800/1df752a3-787a-b7d1-4bf4-f492ff4e330c.png)

# Fortranとは

大規模数値計算で使われる言語です. 速い, (使い)易い, (配列操作が)上手いです.
感想として, AtCoderに向いている言語だと思います.
「Cより便利だが, C++の方が色々あって便利そう」という印象です.

# AtCoder青とは

## AtCoder公式曰く

https://info.atcoder.jp/utilize/jobs/rating-business-impact

では
> Rating 1600以上 (青色)
AtCoderにおける分布(2023/11/20現在)
> 実レーティング分布： 上位3.609%
内部レーティング分布： 上位5.725%
期待できる能力
> 普通のITエンジニアから見て、常軌を逸したコーディング速度を持ち、複雑なロジックにおいてもバグの少ない安定したロジック構築が可能となります。
大抵の業務においてはここまでのレーティングは必要とはなりませんが、例えば、大きなデータを扱う・数理的な処理を扱う・研究開発に近い業務を行う・論文などをキャッチアップして実装までするような業務を行う場合は、大きな力となります。
競技者としては、旧帝大や早慶などの、競プロ強豪校を除いた、大学のエース選手がこの水準です。よほど関連した業務などを行っていない限りは、競プロの練習なしにこの水準のパフォーマンスが安定して出せるITエンジニアはいないと言っても良いでしょう。

...なんかすごそうです.

## 〜考察という名の個人的な感想〜
私の感覚としては, 研究のプログラミングがよく分からなくてイライラ(?)することが少なくなったり, 簡単なプログラムを書く心理的障害がなくなったりなど, プログラミングに慣れた感があります.

### 水色時代の私との違いは...解く速さが上がった気がします?
- ABC364
![Screenshot from 2024-10-21 23-51-52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2296800/4b7db26d-5c6e-98ec-438e-e863308f84dd.png)

- ABC320
![Screenshot from 2024-10-21 23-52-21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2296800/733809db-594c-54de-3e45-2f53a3f92111.png)

あんまり変わらない? とりあえず, コンテスト毎のAC時間の積み上げ棒グラフ(ペナルティ考慮なし)を夜なべしてプロットしてみました.

![times.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2296800/9bc946a2-13ea-5628-4bf6-ecaf87ac1b4b.png)

うーん... プロットしても特徴的なものは見えませんね... 右の方が60分くらいでE問題まで解けているコンテストが多い? ABC問題を解く速さはあんまり変わっていないように見える?


### [AtCoder Graphs](https://atcoder-graphs.vercel.app)(今までのパフォーマンスの寄与を大きさで教えてくれるサイト)によると...
![atcoder_graph.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2296800/804115fc-d3cf-87a0-aee1-d1a7802ea408.png)

...直近で良い順位(パフォーマンス2000くらい)を2回取っていることが効いているのでしょうか? それとも, 水色パフォーマンス(1200〜1599)を安定して取れていることが効いているのでしょうか?

### 軌跡
![atcoder_rating_comments.png.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2296800/cc7203bc-bc78-f8ae-30a2-db77c1454a09.png)

図に何が効いていそうかを書き込んでみました.
[鉄則本](https://book.mynavi.jp/ec/products/detail/id=131288)とはE869120さん著の([緑色までを対象](https://info.atcoder.jp/more/contents/official-book), もしくは[水色までを対象](https://youtu.be/p5uTK_ygYqk?list=PLLeJZg4opYKY2vLnqkPSGgT4iOrIwhbHq&t=1828)とした?)本です.
2024年1月くらいからライブラリの整理とJOI埋めを行っています.
また, 2024年6月と7月は後述の[AtCoder Daily Training](https://atcoder.jp/contests/adt_top
)(ADT)の皆勤賞を取っていたりしています.
ライブラリとJOI埋めとADTの相乗効果でレートが上がったのでしょうか?

# 水色から青色になるためにやったこと

思い返してみると, 「難しい問題を解く」と「問題を速く解く」というのが重要な気がします.
皆が解けていない難しい問題を解くとレートが上がり, 問題を速く解くとレートが下がりにくくなる感じですかね. (私の問題を解く速さが上がっているかは不明です.)

## 自作ライブラリの整理(速解き, 利便性, 難しい問題に貢献?)
今まではコピー＆ペーストでライブラリを貼り付けていたのですが, [fypp](https://github.com/aradi/fypp)(マクロ展開できるやーつ)を有効活用できるように, [自作ライブラリ](https://github.com/osada-yum/Fortran_competitive_library)を改造しました.

[前回の色変記事](https://qiita.com/osada-yum/items/fdc6ec8ff1436258ed01)で
「C++ の template みたいなものがないため, データ構造を入れ子にする場合に面倒.」
と書きましたが, `fypp` でうまいことやれば簡単に作れることが判明しました. (タプルの優先度付きキュー, 7組変数のセグメント木, 自作文字列型の探索木などなど...)

`fypp`の何が良いかというと, 以下のような`fypp`の命令(`#:`で始まっているもの)
```sample.fypp
#:set TUPLE2_ITEM1_TYPES = ["integer"]
#:set TUPLE2_ITEM2_TYPES = ["integer"]
#:set TUPLE2_ITEM1_KINDS = ["int32"]
#:set TUPLE2_ITEM2_KINDS = ["int64"]
#:set TUPLE2_USE_MODULES = []
#:include "src/tuple2_m.fypp"

#:set UNWRAPPED_VECTOR_ITEM_TYPES = ["type"]
#:set UNWRAPPED_VECTOR_ITEM_KINDS = ["tuple2_int32_int64"]
#:set UNWRAPPED_VECTOR_USE_MODULES = ["tuple2_m"]
#:include "src/unwrapped_vector_m.fypp"
```

を書くことで, 一つ目が `integer(int32)` で 二つ目が `integer(int64)` の `tuple2` を展開できます. また, `tuple2の可変長配列`も展開できます. (C++で言うなら`vector<pair<int32_t, int64_t> >`.)
...つまり, コピペするよりも行数が少なく, ジェネリクスの様に型を後から変えられるのでとても楽です.
難しい問題では, 複雑なデータ型を要求されることがあるので, `fypp` はを導入して良かったと思います.

## JOI埋め(難しい問題に貢献?)
[こちらのサイト](https://joi.goodbaton.com)のLevel5 〜 Level7を解きました.

https://joi.goodbaton.com

レベル毎に分かれているので, たくさん解きました.
感想としては, Level5の問題は直ぐに解けましたが, 6と7は結構大変だったので, たくさん時間掛けて解きました.
また, レベル毎に分かれているので, 徐々にステップアップできる上, 教育的な問題が詰まっていると思います. おそらく, そのLevel帯なら知っておいてほしい問題なのだと思います.

## AtCoder Daily Training(速解きに貢献?)
https://atcoder.jp/contests/adt_top

過去のコンテストの問題がランダムに出てくるやつです.
反復練習をすることで問題を解くことに慣れるのに貢献していると思います.
感想としては, A〜C問題を解く速さを上げると, D問題以降を解く時間が増えるため, A〜C問題に慣れると有利だと思います. もしかしたら, のーみその負荷が減って調子が良くなる効果もあるかもしれません.

# おまけ
少しは貢献しているかもしれない要素とかFortranへの想い.
## 他の言語にも触ってみる(脳みその柔らかさに貢献?)
C, C++, R, Emacs Lisp, Common Lisp, Scheme, Haskell, Java, Lua, Ada, Pascalなどに触れて分かったことは...
「Fortranはそんなに悪くないのでは?」です.
以下が競技プログラミングの最初の難しいところだと思うのですが, Fortranは普通くらいにはできると思います.
- 「入力を読み込んで結果を出力する」
   Fortranの場合は`read`文があるので割と容易だなと思いました. (ただ, 一部の問題はFortranを殲滅しようとしています. [これ](https://atcoder.jp/contests/abc310/tasks/abc310_c)とか.)
   ```read_mul.f90
   program read_mul
      implicit none
      integer :: x, y
      read*, x, y
      print*, x * y
   end program
   ```
   で整数2つ読み込んで, 整数同士を掛けたものを出力できます.

   実行
   ```bash
   $ gfortran read_mul.f90 -o read_mul.out
   $ ./read_mul.out <<< "42 3"
         126
   ```

   ```read_arr.f90
   program read_arr
     implicit none
     integer :: n
     integer, allocatable :: arr(:) ! 動的にメモリ確保できる配列.
     read*, n                      ! 配列のサイズ読み込む.
     allocate(arr(n))              ! 配列を確保する.
     read*, arr(:)                 ! 配列にn個の値を読み込む.
     print*, arr(:)                ! 配列の値を全て出力する.
   end program
   ```
   で配列も簡単に入出力できます.

   実行
   ```bash
   $ gfortran read_arr.f90 -o read_arr.out
   $ ./read_arr.out <<< "4
   42 0 -10 3"
          42           0         -10           3
   ```

- 「計算する, 配列を弄る」
   Fortranは`include`とか`import`なしでできるので容易な気がします.
   例えば, `integer` の冪乗は 
   ```pow.f90
     x = 3**4
   ```
   で計算できます(C, C++の`pow`関数は`pow(a, b) == exp(b*log(a))` [らしいです?](https://cpprefjp.github.io/reference/cmath/pow.html). なので`int`を`pow`すると誤差が発生する落とし穴があります).
   配列の最大値を求めるには 
   ```maximum.f90
     x = maxval(arr(:))
   ```
   です(C++では`<algorithm>`を`include`して, `*max_element(arr.begin(), arr.end())`なので, Fortranの方が楽な気がします. ただ, C++は[`lambda`式に基づく最大値を求めることができる](https://cpprefjp.github.io/reference/algorithm/max_element.html)ので, クラスの最大値を求める場合にはC++が有利ですが).
- 「文字列を良い感じにする」
   微妙な感じです. 固定長文字列なので, 扱いに癖がある気がします. 文字列を操作する関数があんまりないですが, 標準ライブラリを使うだけで解ける問題はそんなにないので, まあ良いかという感じです.
   また, 文字列を空白で区切る関数はありませんが, 空白で区切られた`N`個の文字列を読み込むことは簡単です.
   ```read_strs.f90
   program read_strs
      implicit none
      character(len=10) :: a, b, c
      read*, a, b, c
      print*, "|"//a//"|"
      print*, "|"//b//"|"
      print*, "|"//c//"|"
   end program
   ```
   実行
   ```bash
   $ gfortran read_strs.f90 -o read_strs.out
   $ ./read_strs.out <<< "abc edf ghdshgs"
    |abc       |
    |edf       |
    |ghdshgs   |
   ```
   このように, 空白で区切られた文字たちを読み込めます. 文字列は`//`で結合できます.

## 結局Fortranってどーなの?
頑張れば結構使えます. ただ, C++やPython3なら標準ライブラリにある `平衡二分探索木`(set) を自作しないといけないので, ハードルが高い気がします. また, ジェネリクスみたいなものがないため, `fypp` のようなツールに頼らなければ辛いです. 盤外戦を制しましょう.
~~素直に他の言語を使いましょう~~ **Fortranと共に生きることを決意して全てを自作しましょう**.

# まとめ
なんで青色になれたか分かりましたか? 私にはあんまりよく分かりませんでした. おそらく, E問題までを速く解けば良いのだと思います...?

(2024/10/30追記) もしかしたら, 「あんまりよく分からない」ということが重要で, 「飛躍的な成長」ではなく「継続的な成長の積み重ね」が重要なのかもしれません.
end