codefestival final C Time Gap

問題

コード (2WA間違いコード)

int N;

int pot(int a,int b){
    return ((a*b)?max(abs(a-b),abs(24 - a - b)):max(a,b));
}

int main(){
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;

    vector<int> d(N+1,0);
    vector<int> ct(13); //カウント用
    ct[0] = 1;
    REP(i,N){
        cin >> d[i]; //0:高橋くん,1~N:参加者
        ct[d[i]]++;
        if(ct[d[i]]==3){
            cout << 0 << endl;
            return 0;
        }
    }

    int ans = 12;

    for(int i = 0;i < N;i++){
        for(int j = i+1;j <= N;j++){
            int tmp = pot(d[i],d[j]);
            chmin(ans,tmp);
        } 
    }

    cout << ans << endl;
}

自分の方針

d[i] d[j] が与えられた時、その二人の時差の最小値の最大値を返す関数 pot を作って、それをN+1人に対し計算し、その最小値を出力した。 しかしこれでは例えば、高橋くんとの時差 t に 一人しかいないときでも、t と 24-t に両方いるようにみなしてしまっているので、誤りだった。 解説では、3つ以上同じ d[i] がきたら0を出力し、そうでないときは、一人なら t と 24-t のそれぞれ２通りに置いてためす、二人なら両方に配置するといいと書いてあった。 考察不足...。

ABC 088 D - Grid Repainting

問題

atcoder.jp

コード

typedef pair<int,int> pii;

int main(){
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W;
    cin >> H >> W;

    char s[100][100];
    vector<vector<int>> dist(H,vector<int>(W,-1));

    

    int ct = 0;
    rep(i,H)rep(j,W){
        cin >> s[i][j];
        if(s[i][j] == '.')ct++;
    }

    queue<pii> q;
    dist[0][0] = 1;

    q.push(pii(0,0));
    while(!q.empty()){
        pii r = q.front();
        q.pop();
        if(r.first < H-1 && dist[r.first+1][r.second] == -1 && s[r.first+1][r.second] == '.'){
            dist[r.first+1][r.second] = dist[r.first][r.second] + 1;
            q.push(pii(r.first+1,r.second));
        }
        if(r.second < W-1 && dist[r.first][r.second+1] == -1 && s[r.first][r.second+1] == '.'){
            dist[r.first][r.second+1] = dist[r.first][r.second] + 1;
            q.push(pii(r.first,r.second+1));
        }
        if(r.first > 0 && dist[r.first - 1][r.second] == -1 && s[r.first-1][r.second] == '.'){
            dist[r.first-1][r.second] = dist[r.first][r.second] + 1;
            q.push(pii(r.first-1,r.second));
        }
        if(r.second > 0  && dist[r.first][r.second-1] == -1 && s[r.first][r.second-1] == '.'){
            dist[r.first][r.second-1] = dist[r.first][r.second] + 1;
            q.push(pii(r.first,r.second-1));
        }
         
    }

    if(dist[H-1][W-1] == -1) cout << -1 << endl;
    else cout << ct - dist[H-1][W-1] << endl;

}

解法

bfsで最小コストを求め全体の白の個数から引く

ABC016 C - 友達の友達

問題

atcoder.jp

コード

using Graph = vector<vector<int>>;
 
Graph G;
vector<int> ct;
vector<bool> seen;
 
void dfs(int pre, int c, int p,int d){  //pre:スタート, c:探索ノード, p:親, d:深さ
  if(d == 2){
    for(auto i:G[c]){
      if(i == pre) return;
    }
    if(seen[c]){
      ct[pre]++;
      seen[c] = false;
    }
  }else{
    for(auto j:G[c]){
      if(p != j){
        dfs(pre,j,c,d+1);
      }
    }
  }
}
 
int main(){
  //cout.precision(10);
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N,M; cin >> N >> M;
  
  G.resize(N);
  ct.assign(N,0);
  
  
  rep(i,M){
    int a,b;
    cin >> a >> b;
    --a;--b;
    G[a].PB(b);
    G[b].PB(a);
  }
  
  rep(i,N){
    seen.assign(N,true);
    dfs(i,i,-1,0);
    cout << ct[i] << endl;
  }
 
}

解法

深さ2までのdfsを実装した。違う経由点から同じ友達の友達に行く経路でダブルカウントしてしまっていたので、seenを導入した。

diverta 2019 Programming Contest 2 B - Picking Up

問題

atcoder.jp

コード

int main(){
  //cout.precision(10);
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N;cin >> N;
  vector<pair<ll,ll>> x(N);
  rep(i,N) cin >> x[i].first >> x[i].second;
  sort(ALL(x));
  
  pair<ll,ll> a[100][100];
  
  map<pair<ll,ll>,ll> mp;
  
  rep(i,N){
    for(int j = i + 1;j < N;j++){
        a[i][j].first = x[j].first - x[i].first;
        a[i][j].second = x[j].second - x[i].second;
        mp[MP(a[i][j].first,a[i][j].second)]++;
    }
  }
  
  int max = 0;
 
 
  for(auto i:mp){
    chmax(max,i.second);
  }
  
  
  cout << N - max << endl;
  
  
}

解法

i,j(i<j)について各(x[j]-x[i],y[j]-y[i])を計算し、もっとも多いものの個数を元の個数から引いた。 mapのvalueが最大になるkeyを取得する方法がわからず大人しくforloopを回した。

ABC037 C - 総和

問題

atcoder.jp

コード

ll N,K;
 
ll func(ll l,ll r){
  if(l >= K - 1 && r >= K - 1)return K;
  chmin(l,K-1);chmin(r,K-1);
  return max((ll)0,l + r - K + 2);
}
 
    
 
int main(){
  //cout.precision(10);
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  cin >> N >> K;
  
  vector<ll> a(N);
  rep(i,N) cin >> a[i];
  
  ll ans = 0;
  
  rep(i,N){
    //cout << i << ' ' << func(i,N-i-1) << endl;
    ans += a[i] * func(i,N-i-1);
  }
  
  cout << ans << endl;
  
}

解法

単純に２重ループで回すとO(N2)となり間に合わないので、各箇所が何回長さKの部分列に含まれることがあるかを計算し(func)、最後に足し合わせた。 もっと楽に累積和を用意しておけば、O(1)で部分列の和を取得できるので、十分間に合うことを知った。