Google Code Jam Round1C C: Fashion Police

問題

https://code.google.com/codejam/contest/4314486/dashboard#s=p1
J・P・S個（)ずつのジャケットとズボンとシャツを持っている人がいる。
彼の住んでいる世の中は恐ろしい所で、同じ服装をすると逮捕されるらしい（雑な理解）
更に、世知辛い世の中なので、ジャケット・ズボン・シャツのうちの２つが同じ服装もK回までしか許されない。
最大何日この人は警察に捕まらず生きていけるかを答えよ。またその時の服装も出力せよ

考えたこと(Small)

SmallはSが3以下らしいので、
3*3*3の最大27通りの服装から、採用する服装の集合2^27を列挙してみて、題意を満たすかどうかのチェックをしてあげると良い。
ケース数が100あるので、最大計算時間はだが…間に合うかな？
とおもいつつ、半信半疑で実装。
実際自分のマシン環境で２分位かけたら答えを返してくれたのでセーフだった。
(但しfirst tryでは出力値を0-indexingにしてしまうと言う痛恨のミスにより時間切れ)

コード(Small)

int bitCount( int mask ){
   int cnt=0;
   while( mask != 0 ){
      cnt++;
      mask &= mask-1;
   }
   return cnt;
}

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int J,P,S,K;
   cin >> J >> P >> S >> K;
   vector<pair<int,pair<int,int> > > c;
   for( int i =0 ; i < J; i++ ){
      for( int j = 0 ; j <P; j++ ){
         for( int k = 0 ; k < S; k++ ){
            c.push_back( make_pair(i, make_pair(j, k)) );
         }
      }
   }
   int size = c.size();
   int ansMask = 0;
   for( int mask=0; mask < (1<<size); mask++){
      if( bitCount(ansMask) > bitCount( mask ) ) continue;
      bool ok = true;
      map<int,int> ab;
      map<int,int> bc;
      map<int,int> ac;
      for( int i = 0 ; i < size; i++){
         if( mask&(1<<i)){
            int A=c[i].first;
            int B=c[i].second.first;
            int C=c[i].second.second;
            ab[A*10+B]++;
            bc[B*10+C]++;
            ac[A*10+C]++;
            if( ab[A*10+B] > K || bc[B*10+C]> K || ac[A*10+C] > K ){
               ok=false;
               break;
            }
         }
      }
      if( ok ) ansMask=mask;
   }
   cout << "Case #" << loop+1 << ": " <<bitCount(ansMask)<< endl;
   for( int i = 0 ; i < size; i++ ){
      if( ansMask&(1<<i) ){
            int A=c[i].first;
            int B=c[i].second.first;
            int C=c[i].second.second;
            cout <<A+1 <<" " << B+1 <<" " << C+1 << endl;
      }
   }
  }
  return 0;
}

考えたこと(Large)

さて34 pointのlargeである。
とりあえず、J,P,Sの大小関係が決まっているので、小さい方をまず固定して考えよう。
j,pの各組み合わせをK回ずつ使う(K>Sの場合はK=Sとみなすとする)として、sの割当を題意を満たすように上手く調整できないかと考える。
直感的に、
(j=1,p=1)の時にあわせるsは1～K,
(j=1,p=2)の時に合わせるsは2～K+1,
(j=1,p=3)の時に合わせるsは3～K+2,
(中略)
(j=2,p=1)の時に合わせるsは2～K+1,
(j=2,p=2)の時に合わせるsは3～K+2,
…
という風にj,pの値に従いsの使用開始位置をずらすようなコードを書いてみた。 (もちろんsの値がSより大きくなった場合はmodをとって調整する)

どうもうまい具合に重複せずに出力できているようである。
時間も迫っているのでこの実装で題意を満たさない時にエラーを吐くようなエラーコード付きでトライ。
エラーも吐かなかったので提出してみた。結果通った。正直通るとは思っていなかったのでびっくりした。

コード(Large)

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int J,P,S,K;
   cin >> J >> P >> S >> K;
   cout << "Case #" << loop+1 << ": " <<J*P*min(S,K)<< endl;
   map<int,int> ab;
   map<int,int> bc;
   map<int,int> ca;
   for( int j=1; j<=J; j++){
      for( int p=1; p<=P; p++ ){
         for( int s=1; s<=min(K,S); s++ ){
            int a=j;
            int b=p;
            int c=(s+p+j-3)%S+1;
            cout << a << " " << b << " " << c << endl;
            ab[a*100+b]++;
            bc[b*100+c]++;
            ca[c*100+a]++;
            if(ab[a*100+b]>K || bc[b*100+c]>K || ca[c*100+a]>K ){
               cerr<< "ERROR in case "<<loop+1<<endl;
               return 0;
            }
         }
      }
   }
  }
  return 0;
}

考察

…で、なんでこれで通るのよ？と言う話について、
jを1として固定した時について改めて確認する (pを1と固定した場合でも同様に確認できるし、固定する値が1でなくとも同様に確認できる)

SがKより小さい場合、
(j=1,p=1)の時にあわせるsは1～S,
(j=1,p=2)の時に合わせるsは2～S,1
(j=1,p=3)の時に合わせるsは3～S,1,2
(中略)
(j=1,p=P)の時に合わせるsはP～S,1,2,...,P-1
...と、結局j=1のジャケットに対して1～Sの各シャツがP回ずつ使われることになる。
しかし、であるから、この割当は題意を満たす。

SがK以上の場合、
case 1: (j=1,p=1)の時にあわせるsは1～K,
case 2: (j=1,p=2)の時に合わせるsは2～K+1
case 3: (j=1,p=3)の時に合わせるsは3～K+2
(中略)
case K: (j=1,p=K)の時に合わせるsはK～2K,
(中略)
case P: (j=1,p=P)の時に合わせるsはP～K+P
シャツKはcase 1～case Kで必ず利用されていることから、
この割り当て方でK+1回利用されているシャツが存在すると仮定するならば、シャツKが真っ先にK+1回使われているはずである。
ところで、case K+1以降でKが利用されるためには、一周回ってKに到達する必要がある(上手く表現できていない気がするが…)から、
少なくともcase P でのsの割当の最大値であるK+PはS+Kより大きく無くてはならない。
しかし、題意によりP<=Sであるから、これは矛盾である。
よって背理法により、K+1回利用されているシャツは存在しない。

というわけで、直感ではあったけれど、1ずつずらす方法によって上手くK+1回使用される組合せを排除できていることがわかる。

Google Code Jam Round 1C B:Slides!

問題

https://code.google.com/codejam/contest/4314486/dashboard#s=p1
B個の建物があって、それぞれの建物の間に一方通行の動く歩道を作ることを考えている。
建物1から建物Bまでの経路数がちょうどMになるような歩道の引き方を一つ出力せよ。

考えたこと

1からBまでの経路上にループとなる部分が1つでもあると解は無限になるため、基本はループは考えないで良い。
この場合の最大ケースとして、
iがjより小さい任意のi,jについてiからjへの経路を構築した場合を考えると、1からBまでの経路数はであるとわかる。
なので、まずはMがこれより大きい場合についてはIMPOSSIBLEを返して良い。
次に、の内訳を調べてみると、以下の総和として分解できる。
1->Bの枝を引いた場合：1通り
2->Bの枝を引いた場合：1通り
3->Bの枝を引いた場合：2通り
以下同様に、
n->Bの枝を引いた場合：通り

よって、Mの2進数表記を舐めながら対応する部分の枝を張って上げれば良い。

コード

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   long long B,M;
   cin >> B >> M;
   if( M > (1LL<<(B-2)) ){
      cout << "Case #" << loop+1 << ": " <<"IMPOSSIBLE"<< endl;
      continue;
   }
   cout << "Case #" << loop+1 << ": " <<"POSSIBLE"<< endl;
   for( int i = 0 ; i < B-1; i++ ){
      for( int j = 0 ; j < B-1; j++ ){
         if( i<j ) cout <<"1";
         else cout <<"0";
      }
      if( i==0 && M==(1LL<<(B-2)) ){
         cout <<"1";
         M--;
      }
      else if( i>0 && (M&(1LL<<(i-1)))){
         cout <<"1";
      }
      else{
         cout <<"0";
      }
      cout <<endl;
   }
   for( int i = 0 ; i < B; i++ ){
      cout <<"0";
   }
   cout << endl;
  }
  return 0;
}

Google Code Jam Round 1C A: Senate Evacuation

問題

https://code.google.com/codejam/contest/4314486/dashboard#s=p0
政党とか議員とか難しい単語が出てきてる気がするけれど、要するに、
個の部屋に人ずつの人がいて、
一度に1人or2人を部屋から屋外に出すことができる。
どこかの部屋に過半数の人数が存在しないように全員を屋外に出す方法を示せ、と言う問題。

考えたこと

基本は多い部屋から屋外に出していけば良いので優先度付きキュー使ってガシガシ消していけば良い。
サンプルにもあるけれど、A,B,Cの部屋に1人ずつ居る時にA,Bからひとりずつ屋外に出してしまうと、
C部屋1人だけが部屋の中にいると言う題意に背くシチュエーションが発生する点に注意(注1)。

(以下間違った検討)
あと、A部屋5人B部屋4人とか言う場合にA部屋から2人出してしまうとB部屋4人A部屋3人のB部屋過半数部屋になっちゃうので、
最大部屋の人数 == 2番めに人の多い部屋の人数+1の場合は最大部屋から1人だけを出してあげるほうが良さそう(注2)。
(↑今回の解法上で問題にはならなかったけれど、そもそもA部屋5人B部屋4人の時点で題意にそぐわないので、このようなケースは存在しなかった）

よって、
最大部屋の人数＞2番目に人の多い部屋の人数+1 ならば、最大部屋から2人排出
最大部屋の人数=2番目に人の多い部屋の人数+1 ならば、最大部屋から1人排出 ＊(注2)への対応
最大部屋の人数=2番めに人の多い部屋の人数で、現在人の居る部屋が3部屋ならば、最大部屋から1人排出 ＊(注1)への対応
最大部屋の人数=2番めに人の多い部屋の人数で、現在人の居る部屋が3部屋でないならば、最大部屋・2番めに人の多い部屋から1人ずつ排出

とすれば良い。

コード

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int N;
   cin >> N;
   priority_queue<pair<int,int> > pq;
   for( int i = 0 ; i < N; i++){
      int P;
      cin >> P;
      pq.push(make_pair(P,i));
   }
   cout << "Case #" << loop+1 << ": ";
   while(pq.size()!=0){
      pair<int,int> p=pq.top();
      pq.pop();
      pair<int,int> q=pq.top();
      pq.pop();
      if( p.first > q.first+1 ){
         p.first-=2;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else if(p.first == q.first+1 || pq.size()==1 ){
         p.first-=1;
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else{
         p.first-=1;
         q.first-=1;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+q.second);
         cout <<" ";      
      }
      if(p.first!=0 )pq.push(p);
      if(q.first!=0 )pq.push(q);
   }
   cout << endl;
  }
  return 0;
}

微修正

最適手数以外の解でも認めると言うゆるい条件だったからまあ良いか、と言う気分で出してしまったけれど、
あまり筋の良い解法では無い気がした。
「最大部屋の人数=2番めに人の多い部屋の人数で、現在人の居る部屋が3部屋ならば、最大部屋から1人排出」
と言う方針も、最大部屋の人数=1である以外の場合は1人排出する必要無いし。
というわけで、以下のような書き方の方が若干賢い気がする。(Smallでpractice通過済)

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int N;
   cin >> N;
   priority_queue<pair<int,int> > pq;
   for( int i = 0 ; i < N; i++){
      int P;
      cin >> P;
      pq.push(make_pair(P,i));
   }
   cout << "Case #" << loop+1 << ": ";
   while(pq.size()!=0){
      pair<int,int> p=pq.top();
      pq.pop();
      pair<int,int> q=pq.top();
      pq.pop();
      if( p.first >= q.first+1 ){
         p.first-=2;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else if( p.first==1 && pq.size()==1 ){
         p.first-=1;
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else{
         p.first-=1;
         q.first-=1;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+q.second);
         cout <<" ";      
      }
      if(p.first!=0 )pq.push(p);
      if(q.first!=0 )pq.push(q);
   }
   cout << endl;
  }
  return 0;
}

TopCoder SRM 689 Easy: ColorfulGarden

考慮漏れがあったせいで落とした悔しい問題。こいつのせいで青コーダーに落とされた記念すべき問題。修行し直します。

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14243
2行n列のセルにa～zのアルファベットが並べられている。これらを並べ替えることで隣接セルが同じアルファベットとならないようにせよ。
もしそのような並べ方ができない場合は要素数0のベクトルを返せ

考えたこと (若干の間違いあり)

隣接セルが同頑張っても同じアルファベットになってしまうケースってどんなとき？と考えた。
例えば2*3セルの場合、aが3つまでは
a?a
?a?
みたいな起き方をすれば隣接しない(つまり、何らかのアルファベットが列数よりも多く存在する場合は詰む)。
よって、アルファベットをソートして後、大体以下の様な順番で埋めていけば良さそうである。
1638
5274

間違っていた点

よくよく見ていたらレッドコーダーの人がresubmitしているし嫌な予感……とおもいつつ時間内に穴が見つからず。
チャレンジフェーズで落とされた。
もっとよくよく考えると、列数と同じ個数存在するアルファベットは真っ先に処理しないといけない点が抜けていた。
例えば、2*3のセルで、アルファベットがabbbccだとすると、並べ替えた結果は以下のようになる。
acb
bbc

つまり、アルファベットの個数が多い順に埋めてやる必要があった（本当は上にも書いたとおり、最大のやつだけ気を配れば良いのだけども)

コード

vector <string> rearrange(vector <string> garden) {
   vector<string> invalid;
   int size = garden[0].size();
   int cnt[30];
   memset(cnt,0,sizeof(cnt));
   for( int i = 0 ; i < 2; i++ ){
      for( int j =0 ; j < size; j++ ){
         cnt[garden[i][j]-'a']++;
         if( cnt[garden[i][j]-'a'] > size ){
            return invalid;
         }
      }
   }
   vector<pair<int,char> > vec;
   for( char c= 'a'; c <='z' ; c++ ){
      vec.push_back( make_pair(cnt[c-'a'],c));
   }
   sort(vec.begin(),vec.end());
   string s = "";
   for( int i= 0; i < (int)vec.size(); i++ ){
      s+=string(vec[i].first,vec[i].second);
   }
   vector<string> ret(2,garden[0]);
   for( int i = 0 ; i < size*2; i++ ){
      if( i<size ) ret[i%2][i]=s[i];
      else ret[(i-size+1)%2][i-size]=s[i];
   }
   return ret;
}

yukicoder #364: 門松木

問題

No.364 門松木 - yukicoder
すべての隣り合う３ノードが門松列になっている木を門松木と呼ぶ。
入力に木が与えられるので、その部分木である門松木のがもつ門松列の個数の最大値を答えよ

考えたこと

どう見ても木DPです……と思ってからDPを実装可能な状況にするまでに凄い時間かかった。
最終的に、
dp[n][o][f]: ノードnが両端のノードより大きい(o=0)/小さい(o=1)ような、門松木の最大の門松列の数。
但し、f=0の時はparent[n]を考慮せず、nとその子孫のみで門松木を作った場合で、f=1の時にはparent[n]を必ず利用する場合の値（なおかつ、parent[n]を含む門松列もカウントする）を格納するとする。
というdpテーブルに落ち着いた。

fというフラグが入っているのは、dp[n][o][f]の計算にあたって、nの孫の個数が依存するため、
その部分まで吸収した値をdp[n][1-o][1]として持たせよう、という算段である。
（ただそんなけったいなことをしたがゆえにだいぶバグって大変でもあった）

コード

int A[100000];
vector<int> edge[100000];
int parent[100000];
int dp[100000][2][2]; //dp[i][j]... node i as a parent, j=1 must use i's parent
void dfs(int p){
//   //cout <<p<<endl;
   for( int i = 0 ;i<(int)edge[p].size();i++){
      int nxt = edge[p][i];
      if( nxt!= parent[p] ){
         parent[nxt]=p;
         dfs(nxt);
      }
   }
}
int ans = 0;
int calc( int p ,int o, int f){
   map<int,int> m;
   //cout << p <<", "<< o <<", "<< f<<endl;
   if(dp[p][o][f]!=-1 ) return dp[p][o][f];
   for( int ei=0; ei < (int)edge[p].size(); ei++ ){
      int n = edge[p][ei];
      //cout << p <<"- "<< n << endl;
      if( n==parent[p]) continue;
      calc(n,0,0);
      calc(n,1,0);
      if( A[n]>A[p] &&o==0){
         m[A[n]]=max(m[A[n]],calc(n,1-o,1));
      }
      if( A[n]<A[p]&&o==1){
         m[A[n]]=max(m[A[n]],calc(n,1-o,1));
      }
   }

   map<int,int>::iterator it=m.begin();
   int cnt=0;
   int cnt_wo_parent=0;
   dp[p][o][0]=0;
   dp[p][o][1]=0;
   while(it!= m.end()){
      cnt++;
      dp[p][o][0]+=it->second;
      if( it->first!= A[parent[p]] ){
         cnt_wo_parent++;
         dp[p][o][1]+=it->second;
      }
      it++;
   }
   dp[p][o][0]+=cnt*(cnt-1)/2;
   dp[p][o][1]+=cnt_wo_parent*(cnt_wo_parent-1)/2;
   if( o==0 && A[parent[p]]>A[p]) dp[p][o][1]+=cnt_wo_parent;
   if( o==1 && A[parent[p]]<A[p]) dp[p][o][1]+=cnt_wo_parent;
   ans=max(dp[p][o][0],ans);
   if( parent[p]!=p ) ans=max(dp[p][o][1],ans);
   //cout << p << ", "<< o <<", "<< 0 <<": "<< dp[p][o][0]<<endl;
   //cout << p << ", "<< o <<", "<< 1 <<": "<< dp[p][o][1]<<endl;
   return dp[p][o][f];
}

int main(){
  int N;
  cin >> N;
  for( int i = 0 ; i <N; i++ ){
      cin >> A[i];
  }
  for( int i = 0;  i < N-1 ; i++ ){
      int x,y;
      cin >> x >> y;
      x--;y--;
      edge[x].push_back(y);
      edge[y].push_back(x);
  }
  memset(parent,-1,sizeof(parent));
  if( N <= 2 ){
   cout<<0<<endl;
   return 0;
  }
  int p=0;
  while( edge[p].size() < 2 ) p++;
  parent[p]=p;
  dfs(p);
  memset(dp,-1,sizeof(dp)); 
  calc(p,0,0);
  calc(p,1,0);
  cout << ans <<endl;
  return 0;
}

yukicoder #363: 門松サイクル

問題

No.363 門松サイクル - yukicoder
すべての連続する３つの数が門松列となっているサイクルを門松サイクルという。
木が与えられた後、２頂点ペアをクエリとして与えるので、もともとの木に２頂点をつなげつことでできるサイクルが
門松サイクルであるか否かを答えよ

考えたこと

一番下にある共通の親を求める時に2^k子上の親をそれぞれ保持しといて見つけるアレ。アレの香りが凄いする（名前を思い出せない）
あとアレと同じ感じで2^kだけ上に辿っても門松列が作れるかどうかを保持してればなんとかなりそう。
でもあまりそれ実装したこと無い気がする……と少し日和る。

いや、そもそもN=10^5のノードが全部縦につながってたら10^5のノードが門松列になってるかの判定するから前処理の時点で10^10使ってLTEだったりする……？なんて一瞬血迷いながら解説をチラ見した。

……やっぱもともとの想定で正しかった。ちなみにアレじゃなくてLCAな。
あと、10^5の一直線ノードが門松列になってるのを判定するのは10^5 * log(10^5)なので問題なかった。

ただし、u,v,LCA(u,v)のサイクルが門松サイクルであると調べるためには、結構色々調べないといけない。
具体的には、(u,v,parent[v]) (parent[u],u,v), LCA(u,v)とその両脇のチェックが必要。あと、2^kの情報を上手くつかいながら　u～LCA(u,v)やv～LCA(u,v)が門松列かの判定も必要。
あと、LCA(u,v)がuに等しい時はLCA(u,v)の両脇という概念がないので、特殊処理が必要である。

コード

かなりごちゃごちゃ。滅茶苦茶時間かかったし凄いバグった。
LCAはライブラリ化するにしても、これを本番に解ききる実装力と頭の良さは鍛えていかないとなぁ。

bool kadomatsu(int x,int y, int z){
   if( x==y || y==z || z==x ) return false;
   if( x<y && y>z ) return true;
   if( x>y && y<z) return true;
   return false;
}

int depth[100000];
int parent[18][100000];
int val[100000];
bool iskadsequence[17][100000];
vector<int> edge[100000];

int up(int cur, int d){
   if( d==0 ) return cur;
   int ex=0;
   int ret = cur;
   while( (1<<ex)*2 <= d ) ex++;
   while( d!= 0&&ex>=0 ){
      if( (d&(1<<ex))!=0){
         ret = parent[ex][ret];
         d-=(1<<ex);
      }
      ex--;
   }
   return ret;
}
int lca(int u, int v){
   if( u==v ) return u;
   int left=0;
   int right=depth[u];
   while( left+1 < right ){
      int mid=(left+right)/2;
      if( up(u,mid)==up(v,mid) ){
         right = mid;
      }
      else{
         left=mid;
      }
   }
   return up(u,right);
}

bool checkKadSeq(int u, int d){
   if( d<= 1 ) return true;
   int ex=0;
   while( (1<<ex)*2 <= d ) ex++;
   if( iskadsequence[ex][u]== false ) return false;
   if( d==(1<<ex) ) return true;
   int p = parent[ex][u];
   if( !kadomatsu(val[parent[0][p]],val[p],val[up(u, depth[u]-depth[p]-1)]) ) return false;
   return checkKadSeq(parent[ex][u], d-(1<<ex));
}

int main(){
   int N;
   scanf("%d",&N);
   memset(depth,-1,sizeof(depth));
   memset(parent,-1,sizeof(parent));
   memset( iskadsequence,false,sizeof(iskadsequence));
   for( int i = 0 ; i < N; i++ ) cin >> val[i];
   for( int i = 0 ; i <N-1; i++ ){
      int x,y;
      scanf("%d%d",&x,&y);
      x--;y--;
      edge[x].push_back(y);
      edge[y].push_back(x);
   }
   stack<int> st;
   st.push(0);
   depth[0]=0;
   parent[0][0]=-1;
   while( !st.empty() ){
      int cur = st.top();
      st.pop();
      for( int ei=0; ei < (int)edge[cur].size(); ei++){
         int nxt = edge[cur][ei];
         if( depth[nxt]!=-1  ) continue;
         depth[nxt]=depth[cur]+1;
         parent[0][nxt]=cur;
         iskadsequence[0][nxt]=true;
         int tmpCur=cur;
         int tmpNxt=nxt;
         for( int i = 0;parent[i][tmpCur]!=-1;i++){
            parent[i+1][nxt]=parent[i][tmpCur];
            iskadsequence[i+1][nxt]=(iskadsequence[i][nxt]&iskadsequence[i][tmpCur]&kadomatsu(val[parent[0][tmpCur]],val[tmpCur],val[tmpNxt]));
            tmpCur=parent[i][tmpCur];
            tmpNxt=parent[i][tmpNxt];
         }
         st.push(nxt);
      }
   }
   int Q;
   scanf("%d",&Q);
   for( int i = 0 ; i < Q; i++ ){
      int u,v;
      scanf("%d%d",&u,&v);
      u--;
      v--;
      if( depth[u] > depth[v] ){
         swap(u,v);
      }
      if( parent[0][u]==v || parent[0][v]== u){
         printf("NO\n");
         continue;
      }
      int v2=up(v,depth[v]-depth[u]);
      if( v2 == u ){
         int child_v=up(v,depth[v]-depth[u]-1);
         if( checkKadSeq(v,depth[v]-depth[u])
             && kadomatsu(val[parent[0][v]],val[v],val[u])
             && kadomatsu(val[child_v],val[u],val[v])){
                    printf("YES\n");
         }
         else{
            printf("NO\n");
         }
         continue;
      }
      int p=lca(u,v2);
      int child_u=up(u,depth[u]-depth[p]-1);
      int child_v=up(v,depth[v]-depth[p]-1);
      if( kadomatsu(val[child_u],val[p],val[child_v])
            && checkKadSeq(u,depth[u]-depth[p])
            && checkKadSeq(v,depth[v]-depth[p])
            && kadomatsu(val[u],val[v],val[parent[0][v]])
            && kadomatsu(val[v],val[u],val[parent[0][u]])
            ){
            printf("YES\n");
      }
      else{
            printf("NO\n");
      }
   }
   return 0;        
}

yukicoder #362: 門松ナンバー

問題

No.362 門松ナンバー - yukicoder
3桁以上の連続する3桁がすべて門松列である数字を門松ナンバーと呼ぶ。
N番目の門松ナンバーを答えよ。

本番で考えたこと (誤っている方法）

ご丁寧に最大ケースの解を出してくれていて、なおかつ14桁であるという事がわかる。これは桁ごとに計算するDPっぽい。
dp[d][n][f]... d桁で最上桁(d桁目)がnであり、d-1桁目の値＞d桁目の値(f=1)である(f=0の時はこの逆)門松ナンバーの数
とかして計算するとどうだろう、と考える。
Nの値がsum{dp[d][n][f]}となるような臨界点を求めて、それベースで最上桁から順に決めていくとか。
=> 実装しながらこの方針だと駄目だ、と気づく。

何故この方針がダメかというと、例えば、N=sum{dp[3][n][f]}+1であるとき、
解は4桁で最上桁が1であることはわかるが4桁で最上桁が1である門松numberの下3桁は、3桁の最小門松ナンバー(102)ではないから。

じゃあどうしよっか……そもそも2桁以下の扱いとか途中に0のある値の処理が大変だぞ……と思ったところで時間切れ。

解説を読んで

２分探索と組み合わせるとは思いつかなかった。
入力Xを与えた時に、dp[d][n][m]][f]：d桁目がn、d-1桁目がmのd桁の数字で、Xの下d桁よりも大きい(f=1) or 以下である(f=0)門松ナンバー
というdp列を用いて、X以下の門松ナンバーの数を数え上げる。
これができればXを二分探索しながら正解を探せば良い。
2桁以下の値とか途中に0が出るケースは頑張る。

コード

#include <iostream>
#include <climits>
#include <vector>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
bool kadomatsu(int x,int y, int z){
   if( x==y || y==z || z==x ) return false;
   if( x<y && y>z ) return true;
   if( x>y && y<z) return true;
   return false;
}
long long func( long long X ){
   long long ret = 0;
   long long dp[16][10][10][2];
   for( int i=0; i<16; i++ ) for( int j=0; j<10; j++ ) for(int k=0 ;k<10; k++ )for(int l=0; l<2;l++){
      dp[i][j][k][l]=0;
   }
   int offset=0;
   for( int i = 0 ; i < 1000; i++ ){
      int x=i/100;
      int y=(i/10)%10;
      int z=i%10;
      int flag = 0;
      if( X%1000 < i ) flag =1;
      if( x==y || y==z || x==z ) continue;
      if( x<y&&y>z ){
         if( x==0 ) offset++;
         if( X>=i ){
            ret++;
         }
         dp[3][x][y][flag]++; 
      }
      if( x>y&&y<z ){
         if( x==0 ) offset++;
         if( X>=i ){
            ret++;
         }
      
         dp[3][x][y][flag]++; 
      }
   }
   long long curDigit=1000;
   int di=4;
   while(curDigit<= X){
      int curD = (X/curDigit)%10;
      for( int i = 0; i <= 9 ; i++ ){
        for( int j=0; j<=9; j++ ){
         for( int k=0; k <=9; k++){
            if(kadomatsu(i,j,k)){
               if( i> curD ){
                  dp[di][i][j][1]+=dp[di-1][j][k][0];
                  dp[di][i][j][1]+=dp[di-1][j][k][1];
               }
               else if( i< curD ){
                  dp[di][i][j][0]+=dp[di-1][j][k][0];
                  dp[di][i][j][0]+=dp[di-1][j][k][1];
               }
               else{
                  dp[di][i][j][0]+=dp[di-1][j][k][0];
                  dp[di][i][j][1]+=dp[di-1][j][k][1];
               }
            }
         }
        }
      }
      curDigit*=10;
      di++;
   }
   for( int d = 4; d <di; d++){
      for( int i=1; i<=9; i++ ){
         for( int j=0; j<=9; j++ ){
            ret+=dp[d][i][j][0];
            if( d!=di-1 ){
               ret+=dp[d][i][j][1];
             }
         }
      }
   }
   return ret-offset;

}

int main(){
   int T;
   cin >> T;
   for( int ti=0; ti<T; ti++ ){
      long long K;
      cin >> K;
      long long left=101;
      long long right=4e13;
      while( left+1 <right ){
         long long mid = (left+right)/2;
         if( func(mid) < K ) left=mid;
         else right=mid;
      }
      cout << right<<endl;
   }
   return 0;        
}