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

実は今まで毎回直前に解いた問題のコードを貼ったり,なければテンプレを探しに行ったりのですが (え?),流石に事故りそうなので .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 タッチ
      • いい加減赤になるということです
    • 作問
      • すごい人に比べて自分の問題がつまらなすぎるのでもっと面白い問題が作りたい
      • 具体的目標は立てづらいね
  • 他のこと

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

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 のような仕様変更もありアップデートしたらアクセス権などが壊れることもありそう

最小費用流についてのちょっとしたメモ

恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャンルではあるのですが詳しい資料がたくさんあるのでそちらへ

最小費用流のライブラリを整備したい人は、これが今まで見た中で最も一般的な形をしている(fが負って何?)ので頑張って通すと良さそう。 Minimum cost b-flow

フローについて詳しいことが知りたい人には Mi_Sawa さんの記事たちがかなり参考になり、今回はこれを参考にしました
ぼくの考えたさいきょうのフローライブラリ - みさわめも
みなさん大好き組合せ最適化も参考にしました。hosさんやwataさんやtokoharuさんの資料も有名です。

b-flow というのは、各頂点に需給が設定されており、各頂点周りで辺の流量のin/outのバランスがbとなっているものである。(組合せ最適化においてもこの定式化)

これをよく見るs-tフローの形にするには、b(v)>0なるvたちにはs->vに容量b(v)の辺を張り、b(v)<0なるvたちにはv->tに容量-b(v)の辺を張って、s->tにbが正のものの和だけ流せばよい。

最短路問題のようなものを考える場合でも、負の閉路があるかどうかというのが重要で、ないものは保守的(組合せ最適化より)と呼ばれ、そのような場合実行可能ポテンシャルが取れる。 (負の閉路が無いことと同値である) 保守的である場合、例えば Bellman-Ford などで適当にやると実行可能ポテンシャルの1つが取れる。

最小費用流においても残余グラフにおいて負の費用の閉路がないことが最適性を特徴付けるのだが、SSP(蟻本もこれだっけ)のアルゴリズムでは各ステップであるb'があって最適なb'-flow、となる形で流量を保持しつつ、この実行可能ポテンシャルも同時に保持しているということがある(これもあまりわかってなかった) このアルゴリズムでは、cだと負辺がある場合もあるが、前のステップのポテンシャルを用いて簡約距離 (x->yに重みwの辺があるときh(x)+w-h(y) みたいな量、ポテンシャルになってればこれは非負)についての最短距離を求めても同じであることを利用して Dijkstra を使える形にしている (天才)

ちなみに、最小費用流の双対LPを見ると実行可能ポテンシャルですね〜という形をしていて、SSPで得られるポテンシャルが双対問題の解にもなっています。

負の辺があると...怖い!というのは有名なはずだがあまり対処方法は有名でないような。結論から言えば、負のコスト(かつ容量正)の辺を逆に全部使ってしまったことにしてbの値を調整し、逆辺があったことにすると残余グラフが保守的であることにできます。あとは1回Bellman-Fordした後はDijkstraでできます。SSPの計算量は|b(v)|の値に依存してるので計算量に注意が必要ではあります。

これは、上で述べたように、1回ポテンシャルの形にできてしまえば後は非負のままできるというわけで、何もしなくても保守的なグラフであれば、すべての容量が0でもbが0ベクトルのときのb-flowの形になってるので初めのポテンシャルを求めてあげればいいわけです。

容量下限がある場合にも、下駄をはかせたりして解決しがちですが問答無用で下限分だけ使ってbを調整した後上限-下限の辺があることにしてオラクルを呼べばいいです。これも計算量に注意 (misawaさんの記事には逆辺の上限を弄る方法が紹介されていて、天才)

なお、yosupo judgeのはbがでかいので scaling 系とかをやらないと通りません。やりおるわ

拡張ユークリッドの互除法の解の範囲

Modint を実装する過程で、拡張ユークリッドで得られる解の範囲について気になったことがあったことを思い出したので (かつ、あまり言及されているのを見たことがなかったので) メモを残しておきます。

  •  ax + by = 1 の解

 a > b > 0, gcd(a, b)=1 とします (そうでないときは gcd で割ったり符号を変えて解いた後戻せばいいです(gcd の方は割らずに進めてもいいです))

結論から言うと、 -b < x < b,  -a < y < a を満たす解が得られ、過程では overflow を気にする必要はないです。

 x \Leftarrow x + b, y \Leftarrow y - a などすると他の解は得られるので、ギリギリの解が求まっていますね。

  • 雑な説明

 a = bq + r (0 \leq r < b) とすると、 (bq + r)x + by = 1 \Leftrightarrow b(qx + y) + rx = 1 より
 bX + rY = 1 が成り立っているとき、 x = Y, y = X - qY とすると解が得られます。

 -r < X < r, -b < Y < b だとすると、 -b < x < b は言えます。

 y = X - qY = X - floor(a / b) * Y の方ですが、 floor(a/b)=floor((a-r)/b) を使うと言えます。 X, Y は符号が逆な感じになってます

ベースケースや境界をちゃんと言うのは許して

同様にして gcd が 1 でないときも  abs(x) < b / gcd(a, b) かつ abs(y) < a / gcd(a, b) が言えると思います。

  • 宣伝

E - Balanced Piles

F - Paper Cutting

は今年の自信作なのでまだの人は解いて