最小費用流の予習 min cost flow

アルゴリズム

http://www.prefield.com/algorithm/graph/primal_dual.html

• ポテンシャルについては下記

最小費用流

http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout13.pdf

• 図がステップ毎に丁寧に書かれているので理解できた
• 書けそうと思える

実践

• マーブル
  • https://abc004.contest.atcoder.jp/tasks/abc004_4
  • AC. https://atcoder.jp/contests/abc004/submissions/4272722
• E - MinCostFlow
  • https://atcoder.jp/contests/practice2/tasks/practice2_e
  • 解説 https://twitter.com/TeruMiyake/status/1305504444956594177/photo/1
  • 行と列の双方の条件を立てながらいい感じに選ぶ→最小費用流かも。流量とコストを適切に決めるのがポイント🤔

min cost flowを使って解ける問題

• (1800)Chef Monocarp
  • https://codeforces.com/contest/1437/problem/C

注意点

• ✅AC 輪投げ https://atcoder.jp/contests/past202005-open/submissions/22455319
• ACL mincostflowにてcostは0以上である必要がある
• 最大得点→最小コストに読み替えて辺を貼るときにcostが負になるならゲタを履かせる必要がある（2行上の提出を参照）

D - Mixing Experiment abc054_d

Quiz

https://atcoder.jp/contests/abc054/tasks/abc054_d

Submit

https://atcoder.jp/contests/abc054/submissions/4261224

Note

• 3次元DPとはいえ恐れるなかれ

テストケース

• テストケース1, 2は間違ったコードでも通りやすい
• そこでテストケース1に追記したテストケース3を作成
• これが通るようにコーディングした

4 1 1
1 2 1
2 1 2
3 3 10
2 2 2

2

10^6 (100万) 以上のサイズの配列宣言に注意

ll dp[41][401][401];

• この配列をint main()内で宣言したらローカルでREになった
• グローバル変数にしたら解決した
• 40x400x400 = 640万 = 6.4 x 10⁶
• これくらいの大きさの配列を宣言するときは気をつけよう

関連問題

https://atcoder.jp/contests/abc054/tasks/abc054_d

D - Factorization abc110_d

Quiz

https://atcoder.jp/contests/abc110/tasks/abc110_d

Submit

https://atcoder.jp/contests/abc110/submissions/4246912

解法

• editorialや、けんちょんさんの記事と同じ

素因数分解

• 過去の提出から再利用
• 因数に1が含まれないように微修正した

vector<ll> factorization(ll N){
    ll n = N;
    vector<ll> A;
    ll sq = sqrt(n);
    FOR(i, 2, sq+1){
        while(n%i==0){
            n /= i;
            A.push_back(i);
        }
    }
    if(n!=1){
        A.push_back(n);    
    }
    return A;
}

ひっかかりポイント

• nCrにて、フェルマーの小定理を使うために事前計算するが、n=10⁵あたりまでしか計算していなかったら1つWA
• 2 * 10⁵ + α くらいにかなり余裕を持たせて事前計算したらAC

タグづけ

• 今回の記事から要素をタグづけするようにした
• するとタグからも辿れる
• いつもは検索バーから似た問題を探していたが、今後はそれが変わるかも

【マラソンマッチ】A - ツーリストXの旅行計画 一番遠く/近くに行ってみる

Quiz

https://atcoder.jp/contests/rco-contest-2019-qual/tasks/rco_contest_2019_qual_a

• 雰囲気を知るということで軽く参加
• テストケースジェネレータをjavacで生成したりした
• 星のように点がある場合をイメージして、一番遠くに行く戦略を試してみた
• 得点は2511
• 現在の最高点が362万点
• この戦略は全然最適ではないということが分かった

標準入力でテキストを入力してテキストを出力させる

• いつもはojコマンドで済ませていた

./a.out < test/sample-2.in > test/output.txt

公開時間

• コンテスト終了後

ちょっと変更すれば一番近い点に行くこともできる

• 30993点
  • https://atcoder.jp/contests/rco-contest-2019-qual/submissions?f.User=peroon

感想

• ビジュアライザ楽しい
• 最適な答えが1つあるわけではなく、徐々に精度を上げていくのはKaggleなどのコンテストに似ている