スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

CodeChef August Cook-Off

2011/08/22 01:00 ~ 03:30 (JST)
CodeChef August Cook-Off の参加記録

講評によると、今回の問題セットは relatively easier than usual だったらしい。
CookOff で 4 問解けたのは初めてかもしれない。

Tags : プログラミング CodeChef 未解決

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. AC (00:15:01)
B. -
C. AC (00:40:45)
D. 2WA, AC (01:45:48)
E. WA, AC (02:23:35)
Standing : 28/474
Rank (Short) : 39 → 33
Rating (Short) : 1363.202 → 1436.611


問題

問題セットの原文はここを参照。

A. Open the Dragon Scroll
N bit の非負整数 A, B が与えられる。
A', B' を、二進数で表示したとき A, B と同じ個数の 1 をもつ数とする。
A' xor B' の最大値を求めよ。

1 ≦ N ≦ 30
0 ≦ A, B < 2N

B. Angry Chef - Crispy Chips
N 人の人が一列に並んでいる。
108 個の村があり、どの人がどの村の出身かが分かっている。

次の R 個のクエリを処理せよ。

クエリ [i, j]
・ 列の i 番目から j 番目までに同じ村の出身者が K 人以上いるような村はいくつあるか?

1 ≦ N, R ≦ 105
0 ≦ i ≦ j < N

C. Vote for the Noodle Soup
自分と、ほかの何人かが投票する。
+1, -1 という 2 種類の票がある。
同じ人が複数回投票することができて、その場合は最後の票だけが有効になる。

自分は N 回投票する。
自分が投票した各段階において、その時点での票の総和が与えられる。
自分以外で 1 回以上投票したのは少なくとも何人いると考えられるか? 最小人数を求めよ。

1 ≦ N ≦ 1000

D. Rotate the String
文字列 S の k-rotation とは S の末尾 k 文字を S の先頭に移動する操作のことをいう。
たとえば、noodles の 3-rotation は lesnood となる。

文字列 S に対して M-rotation と P-rotation を交互に行うとき、何回目で元の文字列 S に一致するか?

1 ≦ |S| ≦ 5×105
1 ≦ M, P ≦ |S|

E. Collect the Chocolate Chips
問題文中の図 のように、一辺 n の直角二等辺三角形のマス目がある。
Po と Mantis はそれぞれ、マス (1, 1), (n, n) にいる。
各マスにはチョコチップが 0 枚以上 106 枚以下落ちている。

Po は マス (i, j) から (i+1, j-1), (i+1, j), (i+1, j+1) の 3 マスに移動できる。
Mantis は(i, j) から (i-1, j-1), (i, j-1), (i+1, j-1) の 3 マスに移動できる。
ただし、二人は三角形からはみ出る場所には移動できない。

二人は共通のゴール (n, 1) に移動したい。
移動する際に、通ったマスにあるチョコチップを回収することができる。
得られるチョコチップの合計個数を最大化せよ。

2 ≦ N ≦ 500

解答

言語は C++。テンプレはここを参照。

A.
inline int popcount(int x){
x=((x>>1)&0x55555555)+(x&0x55555555);
x=((x>>2)&0x33333333)+(x&0x33333333);
x=((x>>4)+x)&0x0f0f0f0f;
x+=(x>>8);
x+=(x>>16);
return x&0x3f;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n,a,b; scanf("%d%d%d",&n,&a,&b);
int c=popcount(a)+popcount(b);

printf("%d\n",((1<<n)-1)-((1<<abs(n-c))-1));
}

return 0;
}

nA := A を二進数表示したときの 1 の個数
nB := B を二進数表示したときの 1 の個数
とする。

nA + nB ≦ N のときは、上位の bit から優先的に 1 を置くのが最良。
nA + nB > N のときは、上位の bit は 1 のまま残したいので、下位の bit から優先的に 0 にするのが最良。
これらをまとめて書くと、上記コードのようになる。

B.

難しい。 あとで解く。

C.
int main(){
for(int n;scanf("%d",&n),n;){
int user=0;
while(n--){
char vote;
int score; scanf(" %c%d",&vote,&score);

int need=abs(score+(vote=='P'?-1:1));
if(user<=need || (user-need)%2==0) user=max(user,need); else user++;
}
printf("%d\n",user);
}

return 0;
}

自分が +1 に票を入れたとする。 (-1 のときも同様)
今、少なくとも自分以外に m 人の投票者がいたとわかっているとする。

票の値の総和を score と書くと、
自分以外によって score - 1 点分の票が入っていることになる。

m 人で score - 1 点を作ることができるなら、答えは m 人のまま、それより悪くなることはない。
作れないなら、答えを更新しないといけない。
では、どんなときに score - 1 点を作ることができるか?
m ≧ score - 1 が必要なことは明白。
さらに考えれば、 m - (score-1) が偶数であることが必要十分であることがわかる。
m - (score-1) が奇数だと、あと 1 人、追加で投票者が必要になる。

これを N 回の投票について繰り返した結果が答え。
文章よりソースコードを読むほうが伝わりやすいかもしれない。

D.
int getPeriod(char *p) {
int m = strlen(p);
int *fail = new int[m+1];
int j = fail[0] = -1;
for (int i = 1; i <= m; ++i) {
while (j >= 0 && p[j] != p[i-1]) j = fail[j];
fail[i] = ++j;
}
return m-fail[m];
}

int main(){
int T; scanf("%d",&T);
while(T--){
static char s[1000001];
int m,p; scanf("%s%d%d",s,&m,&p);

int len=strlen(s);
strncpy(s+len,s,len);
len*=2;
s[len]='\0';

int period=getPeriod(s);
ll ans=-1,pos=0;
for(int i=0;;i++){
if(i>0 && pos%period==0){ ans=i; break; }
if((i&1)==0) pos+=len-m; else pos+=len-p;
}
printf("%lld\n",ans);
}

return 0;
}

まず、文字列の (最小) 周期を求める。
入力サイズがけっこう大きいので、O(|S|2) はダメ。

周期の求め方は知らなかったけど、有名問題だと思ったから検索してみると、Spaghetti Source の KMP 法のページに載ってた。

ただ、載っていた方法そのままだとなぜかうまくいかなかったので、自分で少し修正した。
S' = S + S
S' の KMP table を fail[0...|S'|] とすると、|S'| - fail[|S'|] が周期になるらしい。

S の KMP table を考えると、
S = abcabcab のようなケースで失敗する。 (周期 8 なのに |S| - fail[|S|] = 3 と報告される)

文字列の周期が分かれば、あとは最初の文字列に戻るまで、rotation をシミュレートすればいい。
この部分は、拡張 Euclid 互除法を使えば log オーダーで解ける気がするけど、高々 2|S| 回の rotation で最初の文字列に戻ることがわかるので、わざわざ高速化する必要はない。
シミュレーションは、文字列を本当に rotate していてはさすがに遅いので、文字列の先頭がどこにあるかだけを見る。

E.
int main(){
int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
static int chip[500][500];
rep(i,n) rep(j,i+1) scanf("%d",chip[i]+j);

ll ans[4];
int i_ans=0;
static ll dp[500][500];
rep(t,4){
memset(dp,0,sizeof dp);
dp[0][0]=chip[0][0];
rep(i,n-1) rep(j,i+1) {
for(int d=-1;d<=1;d++) if(0<=j+d && j+d<=min(i+1,n-1-(i+1))) {
dp[i+1][j+d]=max(dp[i+1][j+d],dp[i][j]+chip[i+1][j+d]);
}
}
ans[i_ans++]=dp[n-1][0];

static int buf[500][500];
memcpy(buf,chip,sizeof buf);
rep(i,n) rep(j,i+1) chip[i][j]=buf[n-j-1][n-i-1];

if(t==1) rep(i,n) chip[i][n-1-i]=0;
}

printf("%lld\n",max(ans[0]+ans[3],ans[1]+ans[2]));
}

return 0;
}

見るからに DP。

二人は最終的に左下のマス (n, 1) に着くので、二人ともが通ることができるマスは対角線上のマスのみ。
各マスにあるチョコチップの数は負ではないので、二人ともが対角線マスを通るようなルートは最適でない。

なので、
a1 := Po が対角線マスを通りうるときの Po が拾うことのできるチョコチップの最大枚数
a2 := Po が対角線マスを通らないときの Po が拾うことのできるチョコチップの最大枚数
b1 := Mantis が対角線マスを通りうるときの Mantis が拾うことのできるチョコチップの最大枚数
b2 := Mantis が対角線マスを通らないときの Mantis が拾うことのできるチョコチップの最大枚数
とすれば、答えは max( a1 + b2, a2 + b1 ) となる。

a1, a2, b1, b2 は普通の DP で求められる。
全体で O(n2)。

配列の添え字を間違って 1WA を出した。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。