B. Unmerge ~部分和問題 subset sum~

// 部分和問題 subset sum
// 部分和でtargetを作ることができるか?を返す
// O(N^2)
bool can_subset_sum(VI A, ll target){
  ll N = SZ(A);
  vector<bool> dp(target+1);
  dp[0]=1;
  rep(i,N){
    ll a = A[i];
    for(int j=target; j>=0; j--){ // 状態jからaだけ足す
      if(dp[j]){
        // そこからの遷移
        ll to = j+a;
        if(to>target)continue;
        dp[to]=1;
      }
    }
  }
  return dp[target];
}

// for codeforces
void solve(){
  ll N;
  cin>>N;
  N*=2;
  VI A(N);
  ll ma=0;
  VI I;
  rep(i, N){
    cin >> A[i];
    if(ma<A[i]){
      I.push_back(i);
      ma = A[i];
    }
  }
  I.push_back(N);
  VI L;
  rep(i,SZ(I)-1){
    ll len = I[i+1]-I[i];
    L.push_back(len);
  }
  if(can_subset_sum(L, N/2)){
    p_yes();
  }else{
    p_no();
  }
}

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

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}

部分和を実現するindexたちを復元するには?

codingame fall-challenge-2020 参加記 ~最後までダイクストラ編~

contest

結果 Gold

f:id:peroon:20201123231039p:plain

  • ビームじゃなくてダイクストラで結構いい位置に行けたが限界を感じ、後半の追い込みはしなかった
  • twitterを見ているとlegendに行けると「おめでとう~」という感じで、終了後の感想戦(twitter, twitcasting)でも貢献できそうに思えた

今後学びたい

  • ラソンの2大手法としての「焼きなまし」「ビームサーチ or chokudaiサーチ」
  • 機会を見て学ばなければ(今回が機会だった説)
  • 公式サイトにはmonte carlo tree searchとも書かれていた。これはTLではあまり見られず、これを使うとワンチャンあるかも

やったこと dijkstra

  • 石の数とBREWを頂点としたダイクストラ。石が「1,2.0,3」ならそのまま頂点ID 1203とする
  • CASTを辺とするが、repeatable可能なものはrepeatできる範囲で増幅しておく。辺のコストはcastable, 得られる利益などから決める
    • コスパが良いならプラス
    • castableじゃないなら(休憩が必要なので)マイナス等
  • 石の評価は青から「1, 2, 3, 4」としたが、前半の青・緑をやや重み付ける人も多かったようだ
  • ダイクストラして、行けるBREWのうち行き先を決めたら経路復元し、その1手目を今回の動作とした

やったこと angry BBA

  • 6回目のbrewで勝負が決まるので、その局面では得られるjewelよりも早く作れることを重視した
    • 勝っている状況なら最速で作る
    • 負けている状況なら逆転できるものだけを狙う

やったこと evaluate learning

  • learn対象について、効率の良さや税金、予約の青石が付いてくるかなどで評価して、その評価が高ければ1番したじゃなくても取りに行くようにした
  • 払う石の「数」と貰う石の「数」の差が少ないほどrepeatableが回ると思ってそれも入れてみたが効かなかった
  • 「+1, +1, 0, 0」などの増えるだけlearnはrepeatable=0なのだが使いやすいという利点もあり、どう評価するべきか迷うが少し加点しておいた

困ったこと TLE

  • ダイクストラがたまにTLEする(50ms時間制限)
  • 頂点ID「9999」などありえないものを除去したとしても頂点数は1000~2000あり、それらから辺を生やすとO(N2)本ほどとなり、ギリギリ
  • 小さい変化のlearnが多い時にたくさん辺が張られるのでTLEしやすくなる
  • learnの最大数を8に絞るなどして抑えたが、それでもたまに発生していた。時間を計測して途中で打ち切るのはやらなかった

codingameで使えそうなURL

C2. Binary Table (Hard Version)

  • Quiz
  • AC
  • 解法
    • 下の2行以外は0になるようにする
    • 最下段2行のみに1がある状態になったら、1を右に寄せていく
    • 右下の2x2領域にのみ1がある状態になるので、その状態になれば最悪でも4手で全て0にできる
  • 感想
    • 最後の2x2領域のパターンが24=16通りあって手書きを避けるようにしてみた→うまくいった
    • 「答えの登録・状態変更・略記」のためにラムダ関数を導入(下記コードでいうreg)したが良かった
    • 筋肉実装問題という印象だが、試みが上手くいったのでやってよかった
// for codeforces
void solve(){
  ll H,W;cin>>H>>W;
  VV A(H, VI(W));
  rep(i,H){
    string s;cin>>s;
    rep(j,W){
      char c = s[j];
      ll v = c-'0';
      A[i][j]=v;
    }
  }

  // 答え
  VV Ans;

  // (y,x,y,x,y,x)の順に入力し、その3点の値を反転させる
  auto reg = [&](ll a, ll b, ll c, ll d, ll e, ll f){
    Ans.push_back({a,b,c,d,e,f});
    // 状態も更新する
    A[a][b] = 1-A[a][b];
    A[c][d] = 1-A[c][d];
    A[e][f] = 1-A[e][f];
  };

  // 下2行を残して他は0にする(下の行に1を押し付ける)
  rep(i,H-2){
    rep(j,W-1){
      if(A[i][j]==0 && A[i][j+1]==0)continue;
      if(A[i][j]==1 && A[i][j+1]==1){
        reg(i,j, i,j+1, i+1,j); continue;
      }
      if(A[i][j]==0 && A[i][j+1]==1){
        reg(i,j+1, i+1,j, i+1,j+1); continue;
      }
      if(A[i][j]==1 && A[i][j+1]==0){
        reg(i,j, i+1,j, i+1,j+1); continue;
      }
    }
  }
  // この結果、最下2段にのみ0,1が存在する
  // 1を右に寄せていく
  rep(i,W-2){
    if(A[H-2][i]==0 && A[H-1][i]==0)continue;
    
    if(A[H-2][i]==1 && A[H-1][i]==1){
      if(A[H-2][i+1]==1){
        reg(H-2,i, H-1,i, H-2,i+1);
      }
      else{
        reg(H-2,i, H-1,i, H-1,i+1);
      }
      continue;
    }

    if(A[H-2][i]==0 && A[H-1][i]==1){
      reg(H-1,i, H-2,i+1, H-1,i+1);
      continue;
    }    

    if(A[H-2][i]==1 && A[H-1][i]==0){
      reg(H-2,i, H-2,i+1, H-1,i+1);
      continue;
    }
  }

  // 最後に右下の処理
  while(true){
    ll cnt=0;
    cnt += A[H-2][W-2];
    cnt += A[H-1][W-2];
    cnt += A[H-2][W-1];
    cnt += A[H-1][W-1];
    if(cnt==0){
      // 何もしなくていい
      break;
    }
    else if(cnt==1 or cnt==2){
      // 0を2つ選ぶ
      VI V;
      rep(i,2){
        rep(j,2){
          ll y = H-2+i;
          ll x = W-2+j;
          if(A[y][x]==0 && V.size()<4){
            V.push_back(y);
            V.push_back(x);
          }
        }
      }
      // 1を1つ選ぶ
      rep(i,2){
        rep(j,2){
          ll y = H-2+i;
          ll x = W-2+j;
          if(A[y][x]==1 && V.size()<6){
            V.push_back(y);
            V.push_back(x);
          }
        }
      }
      assert(V.size()==6);
      reg(V[0],V[1],V[2],V[3],V[4],V[5]);      
    }
    else if(cnt==3){
      VI V;
      rep(i,2){
        rep(j,2){
          ll y = H-2+i;
          ll x = W-2+j;
          if(A[y][x]==1){
            V.push_back(y);
            V.push_back(x);
          }
        }
      }
      assert(V.size()==6);
      reg(V[0],V[1],V[2],V[3],V[4],V[5]);
    }
    else
    // cnt=4
    {
      // どれか3つを反転させてcnt=1に遷移させる
      reg(H-2,W-2, H-1,W-2, H-1,W-1);
    }
  }

  {
    // 全て0になっているか確認
    ll sum=0;
    rep(i,H){
      rep(j,W){
        sum += A[i][j];
      }
    }
    assert(sum==0);
  }
  
  // answer
  ll sz = SZ(Ans);
  debug(sz, H*W);
  p(sz);
  rep(i,sz){
    print_vector(Ans[i]);
  }
}

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

    // input
    ll N; 
    cin>>N;
    
    rep(test_id,N){
      debug(test_id);
      solve();
    }
    
    return 0;
}

C - Knapsack

  • Quiz
  • AC
  • 解説
    • 各荷物1つで条件を満たすかチェックする
    • 満たさなかった場合、荷物の重さは floor(W/2)より小さいか、Wより大きいものしかない
    • floor(W/2)より小さい荷物を貪欲に足していってもWを突然超えることはないので、貪欲に足していって条件を満たすか確認すればよい
  • ポイント
    • 各要素を単体チェックすることで、入力の値域を絞れる
void solve(){
  ll N,C;
  cin>>N>>C;
  debug(N,C);
  ll left = (C+1)/2; // 下限

  VI A(N);
  rep(i, N){
    cin >> A[i];
  }
  if(MIN(A)>C){
    // 容量が小さすぎる場合
    // どうやったって無理
    p(-1);return;
  }

  {
    ll sum = SUM(A);
    if(sum<left){
      // 全部足しても下限に届かないなら無理
      p(-1);return;
    }
  }

  rep(i,N){
    ll w = A[i];
    if(left<=w && w<=C){
      // これ1つでいいじゃん
      p(1);
      p(i+1);
      return;
    }
  }

  // それがないということは、各荷物はleft未満、またはCより大きい
  // Cより大きいものは当然採用しない
  // left未満のものは貪欲に足していってもCを超えることはない
  VI Ans;
  ll sum=0;
  rep(i,N){
    if(A[i]>C)continue;
    sum += A[i];
    Ans.push_back(i);
    if(left<=sum && sum<=C){
      // 条件を満たした
      p(SZ(Ans));
      print_vector(Ans);
      return;
    }
  }
  p(-1);
}

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

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}

B. Toy Blocks

void solve(){
  ll N;
  cin>>N;
  VI A(N);
  rep(i, N){
    cin >> A[i];
  }
  ll sum = SUM(A);
  ll ma = MAX(A);
  ll mi = MIN(A);
  
  // 最終状態は最低でもこの箱数が必要
  ll target = ma * (N-1);
  // 最初の和よりは大きくなる
  chmax(target, sum);

  // 最終箱数は N-1 の倍数である必要
  if(target%(N-1)!=0){
    ll add = (N-1) - target%(N-1);
    target += add;
  }

  ll need = target - sum;
  p(need);
}

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

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}