問題はこちら
No.204 ゴールデン・ウィーク(2) - yukicoder
問題文の解釈が難しかった
「連続した最大D日間の平日を休日とする権利が与えられます(分割してはいけません)」
というのは「Dが4のときxxoxoxx→OOoOoOxとすることは出来ない」というだけの意味ではなく
「{平日}∩{有給を使った日}が2つにわかれていてはいけない」、具体的には「Dが4のときxxoxoxxの真ん中の平日は休めない」という意味だそうだ。
連休i日目から有給を使いはじめるとして、有給の使い方が条件を満たしているか確かめた上で、その時の最長連休を調べれば良い。
最長連休を調べるには前回の問題の答えを流用するのが簡単だと思われる
//前回の流用 int renkyu(char*a){ int s=0,n=0,i; for(i=0;i<44;i++){ if(a[i]=='o'){ n++; s=s<n?n:s; } else n=0; } return s; } int main(){ char s[]="xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx"; //空白14文字の前後にxが15文字の計44文字 char t[50]; int m=0,temp,i,j,f,d; scanf("%d\n",&d); gets(s+15);gets(s+22);s[29]='x'; //sの真ん中の空白部分に読み込む for(i=1;i<30;i++){ //有給をi日目から使いはじめることにする strcpy(t,s); f=0; //fは状態を表すフラグ。i日目からチェックを初めて //初めてoからxに変わった時1に、初めてxからoに変わった時2になる //2回目にoからxに変わった時は、有給が分割されてしまったということなので-1を格納しループから抜ける for(j=i;j<i+d;j++){ if(t[j]=='x'){ if(f==2){f=-1;break;} f=1; t[j]='o'; }else{ if(f==1)f=2; } } if(f==-1)continue; //有給が分割されていれば条件を満たさないので次へ temp=renkyu(t); if(m<temp)m=temp; } printf("%d",m); return 0; }
これを短くするのは大変そう。
ということで、「どの連続した平日で有給を使うか」を考えることにする
例えば、直前に連休がp日、直後にq日ある、連続したr日間の平日で有給を使うと
r>DのときD+max(p,q)日
r≦Dのときp+q+r日の連休を得ることができる
（厳密には有給が分割されてしまう可能性を考慮する必要があるが、そうなるのはp+q+r<Dの場合だけであり、問題の答えには自明な下界Dが存在するので、この場合でも答えに影響はない）
ということでこの方針でとりあえず書いてみる
#define max(a,b) (a>b?a:b) o1,o2,x1=14,d,m,n,t='x'; //mはこれまでの最大値,tは今見てる1つ前の文字,nは今見てる文字 //o1x1o2と並んでいて、o2の先端の文字を読み込んでいき、'x'が現れたところで値の更新をしていく //つまり、連休が終わるたびに「その連休の直前の平日で有給を使う」というのを調べる int main(){ for(scanf("%d",&d);~t;){ n=getchar(); if(n==10)continue; //改行は読み飛ばす if(n=='o')o2++; //oならo2カウンタを増やすだけ //そうでない(即ち今の文字がxの)とき else if(t<n||n<0){ //oからxに変わった直後か最後まで読んだならo2が終わったので、x1で有給を使い各種値の更新 m=x1>d?max(m,o2+d):max(m,o1+o2+x1); o1=o2; o2=0; x1=1; } else x1++; //そうじゃない(前もxで今もx)ならx1カウンタを増やすだけ t=n; //最後に「直前の文字」を更新 } //ループ内ではo2の前を潰すパターンしか見てないので //最後の連休の後ろを潰すパターンを最後に調べる printf("%d",max(m,o1+d)); return 0; }
これをギュッと短くする
ループの中でやってることはif文による分岐と代入だけなので三項演算子でまとめられる
p,q,r=14,d,m; main(n,t){ for(scanf("%d",&d);t;n+11?n+112?t>n|!n?m=r>d?d+q>m?d+q:m:m>(p+=q+r)?m:p,p=q,q=0,r=1:r++:q++,t=n:0)n=~getchar(); m=!printf("%d",p+d>m?p+d:m); }
main第二引数は負の値になっているらしく、tの初期値をいい感じにするために、getchar()に~をつけている
163B
16/06/06追記
fmaxの存在を忘れていた
p,q,r=14,d,m; main(n,t){ for(scanf("%d",&d);t;n+11?n+112?t>n|!n?m=r>d?d+q>m?d+q:m:fmax(m,p+q+r),p=q,q=0,r=1:r++:q++,t=n:0)n=~getchar(); m=!printf("%d",p+d>m?p+d:m); }
162B
16/07/16追記
システムテストに落とされました
原因はここ
else if(t<n||n<0){ //oからxに変わった直後か最後まで読んだならo2が終わったので、x1で有給を使い各種値の更新
これは完全に嘘。正しい条件はt=='o'
更にもう１つ
//oからxに変わった直後か最後まで読んだならo2が終わったので、x1で有給を使い各種値の更新
m=x1>d?max(m,o2+d):max(m,o1+o2+x1);
これも嘘。具体的には「(dより短い平日)(長い連休)(dより長い平日)(短い連休)」というならびが存在して、「長い連休+そのあと有給」が最長になる時にWA
正しくはこう
m=x1>d?max(m,max(o1,o2)+d):max(m,o1+o2+x1);
ということでこれらを踏まえて書き直すと
p,q,r=14,d,m; main(n,t){ for(scanf("%d",&d);t;n+11?n+112?t==-112?m=r>d?fmax(d+fmax(p,q),m):fmax(m,p+q+r),p=q,q=0,r=1:r++:q++,t=n:0)n=~getchar(); m=!printf("%d",p+d>m?p+d:m); }
これもうgetcharを~する意味は無いのでそれをやめて
p,q,r=14,d,m; main(n,t){ for(scanf("%d",&d);~t;n-10?n-111?t==111?m=r>d?fmax(d+fmax(p,q),m):fmax(m,p+q+r),p=q,q=0,r=1:r++:q++,t=n:0)n=getchar(); m=!printf("%d",p+d>m?p+d:m); }
ぐっと睨む。
まずn-111のところは、nの値として-1,111,120しかないので、n&16で代替可能
| n | バイナリ |
|---|---|
| -1 | 1111 1111 |
| 111 | 0110 1111 |
| 120 | 0111 1000 |
t==111のところは、tの値として初期値,111,120しかないので、初期値に0を与えてやることにすればt%2で代替可能
ということで
p,q,r=14,d,m,t; main(n){ for(scanf("%d",&d);~t;n-10?n&16?t%2?m=r>d?fmax(d+fmax(p,q),m):fmax(m,p+q+r),p=q,q=0,r=1:r++:q++,t=n:0)n=getchar(); m=!printf("%d",p+d>m?p+d:m); }
166B
