2021 年振り返り (競プロ視点)

何より,働き始めたことで今までのような時間の使い方ができなくなったのでもう競プロは引退かなと思っていたが,意外にも成果が残せた一年だった.

  • 2月

医師国家試験があった.試験の日に opencup があり,discord にいった記憶

  • 3月

ARC writer をした.結構面白い問題が作れたと思うので解いてほしい.

  • 4月

労働開始

  • 5月

AtCoder 赤になった.これを通せばほぼ確実に赤,という状況で提出する瞬間めちゃくちゃ手が震えた.赤になるまでかなり時間がかかったため嬉しかったようなほっとしたような.

  • 6月

Google Code Jam round 3 で 22 位に入り final 進出した.終了数秒前に submit したら,discord で sigma さんにえっ satashun 通過してるじゃんと言われて結果を知った.数え上げ本当にありがとう.JOI 春合宿で箸にも棒にもかからなかったことが結構人生のコンプレックスだったので,成仏したような感覚があった.問題のレベルや相性はそんなに上振れした感はなかったので,まだ続けていればチャンスがあるかもしれないと思った.

  • 8月

GCJ final があった.テンパってしまったのと多倍長にやられてグダグダな結果になってしまった.オンサイトで出たかったね.有名人たちと会話できて感慨深かった.

仕事が結構体力的&時間的に大変だけど,気分転換レベルでも触っていればまだ強くなれるという感触もあるので,もう少し続けていきたい.現状仕事の勉強といい感じのバランスでやれている気がする.

expander.py スクリプト 自分用

.zshrc に関数を定義 expand-acl a.cpp みたいなのを書くと expanded-a.cpp ができる

expand-acl () {
    dir_cur=$(pwd)
    echo "${dir_cur}"
    dir_acl=path-to-ACL-directory
    echo "${dir_acl}"
    dup_file=${dir_acl}/dup-$1
    cp $1 ${dup_file}
    echo "file copied to ${dup_file}"
    cd ${dir_acl}
    python3 expander.py ${dup_file}
    new_file=${dir_cur}/expanded-$1
    mv combined.cpp ${new_file}
    rm ${dup_file}
    cd ${dir_cur}
}

テンプレ作成コマンド作成

実は今まで毎回直前に解いた問題のコードを貼ったり,なければテンプレを探しに行ったりのですが (え?),流石に事故りそうなので .zshrc に関数書いた

ACL あるので atcoder とそれ以外でテンプレ分けてます

prepare_atc 1.cpp するとテンプレが 1.cpp に貼られて,prepare_atc_many {a..f}.cpp とかすると a.cpp, b.cpp, ..., f.cpp ができます

# prepare cp-template
prepare_atc () { cp path-to-your-template-file $1 }
prepare_gen () { cp path-to-your-template-file $1 }

prepare_atc_many () {
    for x in "${@}"
    do
        echo "atcoder_template copied to ${x}"
        prepare_atc ${x}
    done
}

prepare_gen_many () {
    for x in "${@}"
    do
        echo "template copied to ${x}"
        prepare_gen ${x}
    done 
}

2021 年の目標

  • 生存

    • 現在 24 年連続成功していて偉すぎる
  • 医学

    • 国家試験に受かる,仕事に適合
      • (他の人や,自分の数理的能力などに比べると) 明らかに向いてないので長く続けられるかは不明
      • やっている間は真面目にやりたいと思っているが,変に真面目な部分もあるので病まないようにしたい
  • 競技プログラミング

    • AtCoder 2800, CF 2800 タッチ
      • いい加減赤になるということです
    • 作問
      • すごい人に比べて自分の問題がつまらなすぎるのでもっと面白い問題が作りたい
      • 具体的目標は立てづらいね
  • 他のこと

    • 開発など
      • 思ってたより楽しそうなことがわかり始めてきたので勉強を続けたい

Codeforces で International Grandmaster になった

これは記念記事を残しておくと "達成" したくなくてコンテストに出なくなるのが防げるのではないかという気持ちで書かれた記事です

レートが上がると...嬉しい!

あっとこも 2700 乗ったので頑張りたいね

f:id:satashun:20201102201658p:plain

ARC104 F - Visibility Sequence の別実装例

ネタバレ注意



























解説ではボトムアップ (?) に区間を計算していく方法を紹介していましたが、区間を分割していくという視点でも書くことができ、こちらは意識せずとも 4 乗の解法が作れます。

少し数え方の方針が違って、

区間 [l,r] の中で、-1を見ているような一番右のもの、を固定するとそこの値はできるだけ大きくするのが最適です (そのようなものはleft-to-right maxima であって、左も右も条件がゆるくなる) そこで分割すると、左と右の上限が決まります。

よって f(l, r, mx) : 区間 [l, r] を見ていて全ての値が mx 以下、とすると、上述の点ごとに次の左右のmxの値は1つしか遷移しなくていいので単純なメモ化再帰でよいです。

実装例
Submission #17286157 - AtCoder Regular Contest 104

topcoder plugin 導入

パソコンを買い替えたらtopcoderできなくなったのでpluginを入れ直したらめちゃくちゃ苦労した、最近の記事も全然なかったので

以前のパソコンでは CodeProcessor, FileEdit, TZTester を入れて使っていました (自動で目的のclassを含んだテンプレ、テストコードをを含むcppを生成などをしてくれる)

(これらを設定している記事
TopCoderのプラグイン導入 - itohjamのブログ)

これらを

  • OS : macOS Catalina 10.15.6

でインストールしようとしたら無理だった

結論 :
Ultimate guide to TopCoder plugins - Codeforces
を参考にしたらできた Swistakk orz
これは Errichto が上のリンクの内容をやってみた動画
https://www.youtube.com/watch?v=kZ88uEkneb0

  • 頑張っても TZTester だけ動かなかった
  • moj というのが TZTester の改良版らしいので上のブログに従って導入した
  • 今は CodeProcessor, FileEdit, moj でやってみてる

注意

  • snuke さんもアップデートで壊れて困ってた (違うプラグイン(Greed)だけど)

  • 置く場所も関係あるっぽい
  • macOS は近年 Rootless のような仕様変更もありアップデートしたらアクセス権などが壊れることもありそう