D. Edge Deletion ～MSTとDijkstraは似ている？～

MST?

• minimum spanning tree
• 最小全域木のこと

Dijkstra?

• ダイクストラアルゴリズムのこと

Quiz

• Edge Deletion
• https://codeforces.com/contest/1076/problem/D

解説

• editorialの通り、Dijkstraしつつ辺を追加するごとにカウントアップし、途中で打ち切ればいい

MSTとDijkstraは似ている？

• 最初、MSTで解くのだと思った。しかしそれは間違い
• 下記のグラフを考えてみよう

• Sが始点、Tが終点
• Tがgood vertexとなるためには、最短距離でつながっている必要があり、Dijkstraが適切
• エッジの重みが一律１ならば、MSTでもいいだろう

学び

• MST, Dijkstraは似ているが異なる
• 最短の条件が出てくるならDijkstraをまず検討

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

D. Fun with Integers 図示

Quiz

https://codeforces.com/contest/1062/problem/D

観察

• サンプル1より、a=2からスタートしたときはジャンプを繰り返して戻ってこれる。図示すると、

• aとbが整数倍関係（0倍、1倍は不可。範囲内にあること）にあるとき、このループが作れる
• ループの途中で他のループを組み込むことができる
• よって、全ての整数倍関係(a, b)についてのループが合体できる
• 考えうる組(a, b)で得られる得点の総和が答えとなる

(7, 21)とかも組み込める？

• Yes
• (7, 21)はつながっている
• (7, 14)はつながっている（7と21の間にある7の倍数かつ偶数）
• (2, 14)はつながっている
• 図示すると、下記のように、独立したループが存在しないことが確認できる

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

6月-音楽祭 ～範囲和の最大値～

Quiz

• https://www.hackerrank.com/contests/tkcon/challenges/6-

AC code

• https://www.hackerrank.com/contests/tkcon/challenges/6-/submissions/code/1320248583

公式解説

• https://drive.google.com/drive/folders/1nCXiOd4K1GxJVRazWKUg5cojlJZFRIE5

感想

• すごく典型感があるけれど解説AC
• 累積和・累積Maxの添字のズレに注意が必要

図示

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

D - 日本沈没 (Japan Sinks) JOI

Quiz

https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d

AC code

https://atcoder.jp/contests/joi2019yo/submissions/9864231

補足

• 公式解説 https://www.ioi-jp.org/joi/2018/2019-yo/2019-yo-t4-review.html
• これでなんとなく分かるのだが、実装上の注意ポイントがある
  • １：最初から全部沈没している場合（コーナーケース）
  • ２：高さが同じものがあるので、それらは同時に沈没させる必要
  • ３：高さが同じで連続するものもありうる（例 2 1 1 1 2）
• ３については意識したくないので、C++のuniqueを使って、連続する同じ数字を除去する（工夫ポイント）

2 1 1 1 2 => 2 1 2

• map＜int, vector＜int＞＞ で高さごとに添え字を管理して、高さの低いものから沈没させ、島数のmaxを取ってAC

    // 高さごとにリスト管理
    map<ll, VI> mp;
    rep(i, N){
      ll h = H[i];
      mp[h].push_back(i);
    }

Code

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin >> N;

    VI H(N);
    rep(i, N) cin>>H[i];

    // 最初から全部沈没は除外
    ll sum = 0;
    for(ll h : H) sum+=h;
    if(sum==0){
      p(0);
      return 0;
    }

    if(N==1 || N==2){
      p(1);
      return 0;
    }

    // 同じ高さの連続は除外
    auto it = unique(ALL(H));
    H.erase(it, H.end());
    N = H.size();

    // 高さごとにリスト管理
    map<ll, VI> mp;
    rep(i, N){
      ll h = H[i];
      mp[h].push_back(i);
    }

    ll island = 1;
    ll ma = 1;
    vector<bool> sink(N);
    for(auto pa : mp){
      // ll h = pa.first;
      VI V = pa.second;
      
      for(auto idx : V){
        sink[idx] = true;
        if(idx==0){
          if(sink[idx+1]) island--;
        }
        else if(idx==N-1){
          if(sink[idx-1]) island--;
        }
        else{
          island++;
          if(sink[idx+1]) island--;
          if(sink[idx-1]) island--;
        }
      }

      chmax(ma, island);
    }
    p(ma);

    return 0;
}

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

JOI 古本屋(Books)

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0561

AC code

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4146908#1

要素

• ソート
• 累積和
• DP

解法

• 各ジャンルごとに高い順にソートしてよい
• そしてDP

// ジャンル i までで
// 合計 j 冊売るときの最大価格
ll dp[10][2010];

その他

• 非公式難易度は7
  • https://docs.google.com/spreadsheets/d/1zXDtkFmskO5NSxkqck8uDbcJtAhTVZtzPh2hLw64Sw4/edit?pli=1#gid=2075237676
• ジャンル（種類）を添え字としたDP, 新鮮だった
• 公式解説用意してほしい
  • https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/index.html

Code (抜粋)

// genre iまでで
// 合計j冊売るときの最大価格
ll dp[10][2010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin >> N >> K;

    VV A(10); // 10種のジャンルごとに本を登録
    rep(i, N){
      ll p,g;cin>>p>>g;
      g--;
      A[g].push_back(p);
    }

    // 各ジャンルで高い値段順にソート
    rep(i, 10){
      RSORT(A[i]);
    }

    AccSum Acc[10];
    rep(i, 10){
      Acc[i] = AccSum(A[i]);
    }

    rep(i, 10){
      dp[i][0] = 0;
    }

    // ジャンル0
    FOR(sell, 1, SZ(A[0])+1){
      ll bonus = sell * (sell-1);
      dp[0][sell] = Acc[0].sum(0, sell-1) + bonus;
    }

    FOR(g, 1, 10){ // genre
      FOR(sum, 1, K+1){ // 累計で売る冊数
        dp[g][sum] = dp[g-1][sum];
        FOR(a, 1, SZ(A[g])+1){ // 今回のジャンルを売る冊数
          ll bonus = a * (a-1);
          ll price_sum = Acc[g].sum(0, a-1); // 本自体の売値
          if(sum-a<0) break;
          chmax(dp[g][sum], dp[g-1][sum-a] + bonus + price_sum);
        }
      }
    }

    ll ans = dp[9][K];
    p(ans);
    
    return 0;
}