C - Remembering the Days next_permutation解法 

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

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

    VV A(N, VI(N, -1));

    rep(_,M){
      ll a,b,c;cin>>a>>b>>c;
      a--;b--;
      A[a][b]=c;
      A[b][a]=c;
    }

    ll ma=0;
    VI I;
    rep(i,N)I.push_back(i);

    do{
      // Iの順に行く
      ll sum=0;
      rep(i,N-1){
        ll from = I[i];
        ll to = I[i+1];
        if(A[from][to]==-1){
          sum=-inf;
        }else{
          sum += A[from][to];
        }
        chmax(ma,sum); // 毎回取る
      }
    }while(next_permutation(ALL(I)));

    p(ma);
   
    return 0;
}

最短ハミルトンパス

ライブラリ
  • 頂点数は17以下を想定
  • 隣接行列を与えるとパスを返す関数
// ハミルトンパスが存在するなら返す
// （無いなら空の配列を返す）
// 入力 G : 隣接行列 (adjacency matrix)
// 参考にした : by tatyam
//   atcoder.jp/contests/abc190/submissions/19761405
VI Get_Hamiltonian_Path(VV G){
  ll N = G.size();
  assert(N<30);
  // dp[flag][last]
  // flag : visit flags
  // last : last position
  VV dp(1<<N, VI(N,inf));
  rep(i,N){
    dp[1<<i][i]=0; // 始点のみ訪れた場合
  }
  FOR(after,1,1<<N){
    rep(i,N) if(after & 1<<i){ // iを削る
      ll before = after ^ 1<<i;
      rep(j,N) if(before & 1<<j){
        // beforeの状態でラストがjの点から、iへの遷移
        chmin(dp[after][i], dp[before][j] + G[j][i]);
      }
    }
  }
  ll min_len = inf;
  ll min_last = -1;
  rep(i,N){
    ll all = (1<<N)-1;
    if(dp[all][i] < min_len){
      min_len = dp[all][i];
      min_last = i;
    }
  }
  if(min_len==inf){
    VI path; return path;
  }
  // 復元
  VI path = {min_last};
  ll visit = (1<<N)-1;
  ll last = min_last;
  ll len = min_len;
  while(len){
    rep(i,N) if(visit & 1<<i){
      // iからlastに来たかどうか
      if(i==last)continue;
      ll before = visit ^ (1<<last);
      if(dp[before][i] + G[i][last] == dp[visit][last]){
        // iから来たんだね
        visit = before;
        len -= G[i][last];
        last = i;
        path.push_back(i);
        break;
      }
    }
  }
  reverse(ALL(path));
  return path;
}

verified

abc309_c "C - Medicine" 二分探索解法 

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N,K;
    cin>>N>>K;
 
    VI A(N);
    VI B(N);
    rep(i,N){
      cin >> A[i] >> B[i];
    }
 
    // 1日目からK錠以下かどうか
    if(SUM(B)<=K){
      p(1);
      return 0;
    }
 
    ll left=1; // K錠より大きい
    ll right=inf; // K錠以下
 
    while(right-left>1){
      // centerの日
      ll center = (left+right)/2;
 
      // centerの日に飲むタブレットの合計
      ll tablet=0;
 
      rep(i,N){
        if(A[i]>=center){
          tablet += B[i];
        }
      }
 
      if(tablet<=K){
        right = center;
      }else{
        left = center;
      }
    }
    p(right);
 
    return 0;
}

ABC307 Cなのに水色diffとなってしまった問題「Ideal Sheet」を解いてみた 

VS load(){
  ll H,W;cin>>H>>W;
  VS S(H);
  rep(i,H)cin>>S[i];
  return S;
}

// Aの上にBを描く
VS paint(VS A, VS B, ll dy, ll dx){
  ll H = B.size();
  ll W = B[0].size();
  rep(i,H){
    rep(j,W){
      if(B[i][j]=='#'){
        A[i+dy][j+dx] = B[i][j];
      }
    }
  }
  return A;
}

VS crop(VS A){
  ll H = A.size();
  ll W = A[0].size();
  ll min_y=inf;
  ll min_x=inf;
  ll max_y=-inf;
  ll max_x=-inf;
  rep(i,H){
    rep(j,W){
      if(A[i][j]=='#'){
        chmin(min_y,i);
        chmin(min_x,j);
        chmax(max_y,i);
        chmax(max_x,j);
      }
    }
  }
  VS ret;
  FOR(i,min_y, max_y+1){
    string s;
    FOR(j,min_x, max_x+1){
      s.push_back(A[i][j]);
    }
    ret.push_back(s);
  }
  return ret;
}

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

    // input
    VS A = load(); A=crop(A);
    VS B = load(); B=crop(B);
    VS X = load(); X=crop(X);

    VS plain = VS(20, string(20,'.'));

    rep(dy0,11){
      rep(dx0,11){
        rep(dy1,11){
          rep(dx1,11){
            // paint A
            VS temp = paint(plain, A, dy0, dx0);

            // paint B
            temp = paint(temp, B, dy1, dx1);

            // cut space
            VS cropped = crop(temp);

            if(cropped==X)yes();
          }
        }
      }
    }
    no();
    
    return 0;
}

コーナーケース

  • というべきなのかどうか、最初の提出ではWAになった https://atcoder.jp/contests/abc307/submissions/42956280
  • 下記の画像は実現可能 (Yes) ですが、WAの提出では取りこぼしてしまいます。A, Bにも事前にcropをしておく必要がありました

筋肉解法

  • 上記コーナーケースに気づけなかったとしても、探索範囲を雑に広げることでACできました
  • これは最後の手段でしょう
  • 透明なシートのサイズを20x20 => 40x40
  • オフセットの探索範囲を11 => 21
  • とすることで1.5秒かかりますがAC https://atcoder.jp/contests/abc307/submissions/42959034
    • (A, Bのcropなし)

H - 桁差の和 (第13回 アルゴリズム実技検定) 別解（ソート・二分探索・累積和） 

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N;
    cin>>N;
    string s;cin>>s;
 
    VI A;
    rep(i, N){
      ll a = s[i] - '0';
      A.push_back(a);
    }
    SORT(A);
 
    AccSum Acc(A);
 
    ll sum=0;
    for(ll a : A){
      auto it = lower_bound(ALL(A), a);
      ll i = it - A.begin();
      
      // aの方が小さい部分
      {
        ll num = A.end() - it;
        sum += Acc.sum(i, N) - num*a;
      }
 
      // aの方が大きい部分
      {
        sum += a*i;
        sum -= Acc.sum(0,i);
      }
    }
    p(sum/2);
    
    return 0;
}