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

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

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

Fortranとは

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

AtCoder青とは

AtCoder公式曰く

では

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

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

〜考察という名の個人的な感想〜

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

水色時代の私との違いは...解く速さが上がった気がします?

• ABC364
  

• ABC320
  

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

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

AtCoder Graphs(今までのパフォーマンスの寄与を大きさで教えてくれるサイト)によると...

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

軌跡

図に何が効いていそうかを書き込んでみました.
鉄則本とはE869120さん著の(緑色までを対象, もしくは水色までを対象とした?)本です.
2024年1月くらいからライブラリの整理とJOI埋めを行っています.
また, 2024年6月と7月は後述のAtCoder Daily Training(ADT)の皆勤賞を取っていたりしています.
ライブラリとJOI埋めとADTの相乗効果でレートが上がったのでしょうか?

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

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

自作ライブラリの整理(速解き, 利便性, 難しい問題に貢献?)

今まではコピー＆ペーストでライブラリを貼り付けていたのですが, fypp(マクロ展開できるやーつ)を有効活用できるように, 自作ライブラリを改造しました.

前回の色変記事で
「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埋め(難しい問題に貢献?)

こちらのサイトのLevel5 〜 Level7を解きました.

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

AtCoder Daily Training(速解きに貢献?)

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

おまけ

少しは貢献しているかもしれない要素とかFortranへの想い.

他の言語にも触ってみる(脳みその柔らかさに貢献?)

C, C++, R, Emacs Lisp, Common Lisp, Scheme, Haskell, Java, Lua, Ada, Pascalなどに触れて分かったことは...
「Fortranはそんなに悪くないのでは?」です.
以下が競技プログラミングの最初の難しいところだと思うのですが, Fortranは普通くらいにはできると思います.

• 「入力を読み込んで結果を出力する」
  Fortranの場合はread文があるので割と容易だなと思いました. (ただ, 一部の問題はFortranを殲滅しようとしています. これとか.)

  read_mul.f90

  program read_mul
     implicit none
     integer :: x, y
     read*, x, y
     print*, x * y
  end program
  

  で整数2つ読み込んで, 整数同士を掛けたものを出力できます.

  実行

  $ 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
  

  で配列も簡単に入出力できます.

  実行

  $ 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)) らしいです?. なのでintをpowすると誤差が発生する落とし穴があります).
  配列の最大値を求めるには

  maximum.f90

    x = maxval(arr(:))
  

  です(C++では<algorithm>をincludeして, *max_element(arr.begin(), arr.end())なので, Fortranの方が楽な気がします. ただ, C++はlambda式に基づく最大値を求めることができるので, クラスの最大値を求める場合には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
  

  実行

  $ 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