ABC278 E - Grid Filling ~Aの値域を気にせず(?)mapで解く解法~

  • 問題 https://atcoder.jp/contests/abc278/tasks/abc278_e
  • 提出 https://atcoder.jp/contests/abc278/submissions/36654013 (AC 600ms)
  • 方法
    • 種類数はmap.sizeで求める
    • 除去範囲を1ずつスライドさせてmapを更新する。この更新は差分のみ行い高速化する
  • 計算量
    • 一番重いところは3重ループの箇所で、O(HWN log(N))
    • この解法、Aの値域がN以下のおかげで間に合っていますね。値域に制限がなければmapのサイズがHWになりうるので、300倍遅くなってTLEします

code

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

    // input
    ll H,W,N,h,w;
    cin>>H>>W>>N>>h>>w;

    map<ll,ll> mp_all;
    VV A(H, VI(W));
    rep(i,H){
      rep(j,W){
        ll a;cin>>a;
        A[i][j]=a;
        mp_all[a]++;
      }
    }

    // kの行について解く
    rep(k,H-h+1){
      auto mp = mp_all;
      // 塗りつぶしの分を引く
      rep(i,h){
        rep(j,w){
          ll y = k+i;
          ll x = j;
          ll a = A[y][x];
          mp[a]--;
          if(mp[a]==0)mp.erase(a);
        }
      }
      VI Ans;
      Ans.push_back(mp.size());

      // 右にずらす
      FOR(dx,1,W-w+1){
        rep(i,h){
          // 黒塗りから外れる分
          ll a = A[k+i][dx-1];
          mp[a]++;

          // 黒塗りになる分
          a = A[k+i][dx+w-1];
          mp[a]--;
          if(mp[a]==0)mp.erase(a);
        }
        Ans.push_back(mp.size());
      }
      print_vector(Ans);
    }

    return 0;
}

はじめての「ビームサーチ」に最適なシンプルな問題

  • これ https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_aw
  • 鉄則本を手に入れたのでやってみた
  • 自分流にアレンジを加えつつ1から書いたことで、少しハマったが理解が深まった
    • Beamの状態がメモリを食うのでグローバルに置く必要があった
  • 提出 score=48805 https://atcoder.jp/contests/tessoku-book/submissions/35392329
  • これを叩き台としてAHCでも使っていこう
  • この問題では序盤の得点も響いてくるのでビームサーチで上位を取るのが効くのかな
  • 一方、最終状態でのみスコアが決まるなら焼きなましが向いているのかな

はじめての「焼きなまし」に最適なシンプルな問題

高速化に寄与しなかったもの

  • sqrtが重いと聞くので、距離関数のsqrtを除去→劣化
  • sqrtの高速化バージョンとして公開されているものを使用→変化なし

スコアUPに寄与したもの

  • タイマーで時間いっぱい回す
  • 冷めた時の温度の下限を0.1までさげた(冷やし切るとバグりづらい?)

第九回 アルゴリズム実技検定 G - 連結 ~UF解法~

#include <atcoder/dsu>
using namespace atcoder; // 忘れがち

ll mat[100][100];

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

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

    while(Q--){
      ll ty;cin>>ty;

      if(ty==1){
        // edge
        ll u,v;cin>>u>>v;u--;v--;
        mat[u][v] = 1 - mat[u][v];
        mat[v][u] = 1 - mat[v][u];
      }
      else{
        dsu uf(N);
        rep(i,N){
          FOR(j,i+1,N){
            if(mat[i][j])uf.merge(i,j);
          }
        }
        ll u,v;cin>>u>>v;u--;v--;
        if(uf.same(u,v)){
          p("Yes");
        }else{
          p("No");
        }
      }
    }

    return 0;
}

E - Addition and Multiplication 2 ~DP解法~

// Aの方が大ならtrue
// 等しいならfalse
bool my_compare(VI& A, VI& B){
  if(A==B)return false;
  ll sumA = SUM(A);
  ll sumB = SUM(B);
  if(sumA>sumB)return true; // 桁数で上回る
  if(sumA<sumB)return false;
  // 桁数が同じなら
  for(int i=9; i>=1; i--){
    if(A[i]>B[i])return true;
    if(A[i]<B[i])return false;
  }
  return false; // ここに来ることはない
}

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

    // input
    ll N;cin>>N;

    // dp[i][j]
    // i : i円使った時の最大の値
    // j : 数値jの個数
    VV dp(1000000+5, VI(10));
    
    VI C(10);
    rep(i,9){
      cin>>C[i+1];
    }

    rep(i,N){
      FOR(j,1,10){
        // 番号jをえらぶ
        if(i+C[j]>N)continue; // cost over

        ll to = i+C[j];

        // 上書き候補
        VI candidate = dp[i];
        candidate[j]++;

        if(my_compare(candidate, dp[to])){
          dp[to] = candidate;
        }
      }
    }

    VI ma = dp[0];
    rep(i,N){
      if(my_compare(dp[i+1],dp[i])){
        ma = dp[i+1];
      }
    }
    stringstream ss;
    for(int i=9; i>=1; i--){
      rep(j,ma[i]){
        ss << i;
      }
    }
    p(ss.str());

    return 0;
}