beet's soil

競プロのことなど

CODE FESTIVAL 2016 Final - Day 1

明後日試験だけどコンテストがあるなら出ますよね(

東京まで

さてさんに一緒に東京まで行ってもらえることになったのでついていった。
駅に早く着き過ぎたり新幹線激混みだったり色々あったけど間に合ってよかった。
来年からはしっかり指定席を買おうなという気持ち。

コンテスト

目標はパーカー
【A - Where's Snuke?】
はい。

#include<bits/stdc++.h>
using namespace std;
int main(){
  int w,h,i,j,k;
  cin>>h>>w;
  string s[w][h];
  for(i=0;i<h;i++)
    for(j=0;j<w;j++) cin >> s[j][i];
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(s[j][i]=="snuke"){
	cout << (char)('A'+j) << i+1 << endl;
	break;
      }
    }
  }
  return 0;
}

hとw逆にしていて1分ぐらいロスしてつらかった。

【B - Exactly N points】
なんかどっかで見たようなでも見たことがなかった問題。
にぶたんして余るところだけえいってやる。
(10^7)^2でオーバーフローして1WA ペナルティないとはいえ勿体無い。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,i,j,k;cin>>n;
  int l=1,r=n,m;
  while(l+1<r){
    m=(l+r)/2;
    if(m*(m+1)/2<=n) l=m;
    else r=m;
  }
  for(i=1;i<=r;i++){
    if(r*(r+1)/2-n!=i) printf("%d\n",i);//cout << i << endl;
  }
  return 0;
}


【C - Interpretation】
UnionFindやるだけとおもったらライブラリ間違っていて時間がかかってしまった。
安定の添え字ミスはなかなか気づかない上に重大なので最初に確認しようと思った。

#include<bits/stdc++.h>
using namespace std;
vector<int> r,p;
void init(int size){
  r.resize(size,0);
  p.resize(size,0);
  for(int i=0;i<size;i++) r[i]=0,p[i]=i;
}

int find(int x){
  if(x!=p[x]) p[x]=find(p[x]);
  return p[x];
}

bool same(int x,int y){
  return find(x)==find(y);
}
void unite(int x,int y){
  x=find(x);y=find(y);
  if(x==y) return;
  if(r[x]>r[y]) {
    p[y]=x;
  }else {
    p[x]=y;
    if(r[x]==r[y]) r[y]++;
  }
}

int main(){
  int n,m,i,j,k,l;
  cin>>n>>m;
  init(n+m);
  for(i=0;i<n;i++){
    cin>>k;
    for(j=0;j<k;j++){
      cin>>l;
      unite(i,n+l-1);
    }
  }
  bool f = true;
  for(i=0;i<n;i++) {
    f&=same(0,i);
  }
  cout << (f?"YES":"NO") << endl;
  return 0;
}

【D - Pair Cards】
二部マッチングのライブラリをコピペしてから制約に気づいた(。
なんかmodでえいってやるんだろうなと思って実装したらサンプルが合わない。
m/2の時の場合分けをしなくてはいけなかった。

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,i,j,k,ans=0;
  cin>>n>>m;
  int x[n],y[m];
  memset(y,0,sizeof(y));
  map<int,int> mi;
  for(i=0;i<n;i++){
    cin>>x[i];
    mi[x[i]]++;
    y[x[i]%m]++;
  }
  ans+=y[0]/2;
  y[0]%=2;
  if(m%2==0){
    ans+=y[m/2]/2;
    y[m/2]%=2;
  }
  for(i=1;i<m;i++){
    if(i*2==m) continue;
    k=min(y[i],y[m-i]);
    ans+=k;
    y[i]-=k;
    y[m-i]-=k;
    //cout << i << ":" << k << ":" << ans << endl;
  }
  for(i=0;i<n;i++) {
    k=min(y[x[i]%m],mi[x[i]])/2;
    if(k>0){
      ans+=k;
      y[x[i]%m]-=k*2;
      mi[x[i]]-=k*2;
    }
  }
  cout << ans << endl;
  return 0;
}

ここまではなんか割と調子がいい感じがしていた。
【E - Cookies】
13WAして100分以上かけてなんとか部分点。
dpが二つ添字持てないから計算量落とさなくちゃいけないんだけど思いつかなかったのでmapで殴った。
枝狩りしても1ケースだけ通らなかったのでやけになってunordered_mapに変えたら通った。
ちょくだいさん(すぬけさん)の解説を聞いてなるほどなあという気持ちになった。
満点解法は見たことないオーダーで笑った。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define DEBUG 1000000
struct st{
  ll d,x,p;
  st(ll d,ll x,ll p):d(d),x(x),p(p){};
};
int main(){
  ll n,a;
  cin>>n>>a;
  ll i,j,k,l,b,inf=1<<28;
  if(n>DEBUG||a>DEBUG||n<=a) {
    cout << n << endl;
    return 0;
  }
  ll g[n+1];
  unordered_map<int,ll> gm[n+1];
  fill(g,g+n+1,inf);
  k=n;
  queue<st> q;
  gm[1][0]=0;
  q.push(st(0,0,1));
  while(!q.empty()){
    st s=q.front();q.pop();
    //cout << s.d << ":" << s.x << ":" << s.p << endl;
    if(s.x>n||s.p>=n) continue;
    
    if(gm[s.p].find(s.x)!=gm[s.p].end()){
      if(gm[s.p][s.x]<=s.d&&s.d) continue;
      gm[s.p][s.x]=min(gm[s.p][s.x],s.d);
    }else gm[s.p][s.x]=s.d;

    g[s.p]=min(g[s.p],gm[s.p][s.x]);
    if(g[s.p]>=k) continue; 
    k=min(k,g[s.p]+(n-1)/s.p+1);
    if(s.d+1<k) q.push(st(s.d+1,s.x+s.p,s.p));
    if(s.d+a<k&&s.x) q.push(st(s.d+a,0,s.x));
    
  }
  cout << k << endl;
  return 0;
}

ここまでで150分で30分ぐらいHの考察をしていたけどわからなかった。

【全体】
1780 -> 1818 (+38)
Dまではサクッと解けたのにE部分点がアレだった。
E明らかにオーダーやばい方法だったのでもっと早く方針転換するべきだった。
まあ改善の余地はあると思いますが目標のパーカーがもらえたのでよかったです。

色々

touristなtouristの話を聞いた。
賞金獲得してる日本勢が大体Twitterで見たことがあっておおってなった。
ボードゲームセッションとかあったけど一人だとハードルが高かった。
UFOキャッチャー無理ゲーでは。
体力測定で腰が逝かれた。
太鼓の達人のプロがいた。
座布団積み上げチャレンジがあったらしい(見れなくて残念
チョク・ダーイをやっつける講演を見た。
" o"[bool] はよくあるテクニックらしい(本当か?
エキシビジョン誰も通さないのかと思ってヒヤヒヤしていた。
ホテルのWifiが使えてよかった。
参加記を書くなどしている。
明日起きるの無理では?

もしかしたら追記するかも…