AtCoder Beginner Contest 113

C - ID

問題

C - ID

考察

個にグループ分けされる、順序付きの個の要素があり、グループごとに順番に番号を振って最後に与えられた順に番号を出力する。
愚直に入力をグループ分けしてまずソートして番号を振ったのち、すべての要素を合体して与えられた順にソートし直せばよい。重いけど構造体で管理しようか。

コード

struct city{ll num, pref, year; str id;};
bool comp_year(city a, city b){
  return a.year<b.year;
}
bool comp_num(city a, city b){
  return a.num<b.num;
}

int main(){
  ll n,m;
  cin >> n >> m;
  vector<city> prefs[n];
  REP(i,m){
    city temp;
    temp.num = i;
    cin >> temp.pref >> temp.year;
    temp.pref--;
    prefs[temp.pref].push_back(temp);
  }
  vector<city> all;
  REP(i,n){
    sort(prefs[i].begin(),prefs[i].end(),comp_year);
    ostringstream sout;
    sout << setfill('0') << setw(6) << i+1;
    str pref_str = sout.str();
    REP(j,prefs[i].size()){
      ostringstream sout2;
      sout2 << setfill('0') << setw(6) << j+1;
      str order_str = sout2.str();
      prefs[i][j].id = pref_str + order_str;
      all.push_back(prefs[i][j]);
    }
  }
  sort(all.begin(),all.end(),comp_num);
  REP(i,all.size()){
    cout << all[i].id << endl;
  }
  return 0;
}

D - Number of Amidakuji

問題

D - Number of Amidakuji

考察

横列、高さの縦棒に対して適当に横棒を入れてあみだくじをつくり、一番左から出発して番目に到達するあみだくじの個数を求める。
動的計画法で「高さにおける左から本目へ到達するあみだくじの横棒の置き方」をカウントしていけばよい。からへの推移は、高さでの横棒の置き方すべてに対して、あみだくじとして不適切なものを除いて適宜加算を行う。今回はがキーとなる。
なお、さらに考察するとでも行ける模様。
sigma1113.hatenablog.com

コード

const ll p = 1000000007;

int main(){
  ll h, w, k;
  cin >> h >> w >> k;
  ll dp[h+1][w];
  fill(dp[0],dp[h+1],0);
  REP(i,w){
    if(i==0) dp[0][i] = 1;
    else dp[0][i] = 0;
  }
  REP(i,h){
    REP(j,1<<(w-1)){
      bool ignore = false;
      REP(l,w-2){
        if(j>>l&1&&j>>(l+1)&1){
          ignore = true;
        }
      }
      if(!ignore){
        REP(l,w){
          if(l!=0&&j>>(l-1)&1) dp[i+1][l]+=dp[i][l-1];
          else if(l!=w-1&&j>>l&1) dp[i+1][l]+=dp[i][l+1];
          else dp[i+1][l]+=dp[i][l];
          dp[i+1][l] %= p;
        }
      }
    }
  }
  cout << dp[h][k-1] << endl;
  return 0;
}

雑感

なぜか今回は日曜開催で、参加できず。実は水色CoderになったのでいずれにせよUnratedだったのですが。
Dは難しいですね。