スポンサーサイト

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

CodeChef The March 2011 Cook-Off

2011/03/21 1:00~3:30 (JST)
CodeChef の月一ショートコンテストの参加記録

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

結果

問題を、問題ページの上から順に A, B, .., E と呼ぶことにする。
A. -
B. -
C. AC
D. -
E. 2WA,AC
Standing : 69/334
Rank (Short) : ??? → 74
Rating (Short) : ??? → 1207.825


簡単な問題は問題文が長くて、問題文が短い問題は難しい。
英文を読むのにつかれた。

問題

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

A. Exponentiation Commutativity
素数 p に対して、次の性質をみたす整数の組 (m, n) はいくつあるか? mod 1000000007 で答えよ。
・ 1 ≦ m ≦ p・(p-1)
・ 1 ≦ n ≦ p・(p-1)
・ p は nm - mn を割り切る

2 ≦ p ≦ 1012

B. Grouping Chefs
N 人のシェフがいて、「シェフ i とシェフ j は仲が良い」という関係が M 個ある。
シェフ i は 2ci の能力を持っている。

何人かのシェフを集めてグループを作ることができる。
グループに属する任意のシェフの組は仲が良くないといけない。
グループの能力はグループに属するシェフの能力の合計である。
能力が高いグループを、上から K 個求めよ。

1 ≦ N ≦ 10000
1 ≦ M ≦ 20000
1 ≦ K ≦ 50
0 ≦ ci ≦ 109
ci ≠ cj ( i ≠ j )

C. Money Transformation
所持金を A ドル B セントとする。
A > 0, C > B のとき、任意のタイミングで 1 ドルを 100 セントに両替してよい。

所持金が C セント以上のとき、
「 C セントを払い、払った後の所持金のドル数とセント数を交換する」
という操作を考える。
( たとえば、C セント払った後に A ドル B セント持っているときは、B ドル A セントになる。)

この操作を好きなだけ行うとき、所持金が最大になるまでの操作の回数を求めよ。

D. Palindrome Palindrome
A を空でない文字列、Ar を A を逆順にしたものとする。
AArAAr という形の文字列を beautiful な文字列と呼ぶことにする。
与えられる文字列 S の中に、beautiful な部分文字列はいくつあるか?

S の長さ ≦ 100000.
S はアルファベット小文字のみからなる。

E. Snake Snaky
Snake というゲーム (見たことある人は多いと思う。こことかここを参照) を考える。
フィールドの大きさを N × M とする。
蛇のスタート位置と、最初の L-1 ステップの移動履歴 (移動した方向) が与えられる。
蛇の長さを L とする。
つまり、最初の L-1 ステップでは蛇は長くなる (尻尾の先端の位置は固定) が、それ以上は長くならない。

L ステップ目以降で何も操作しなかったとき、あと何ステップでゲームオーバーになるか。
またそのとき、壁にぶつかるか自分自身にぶつかるかを求めよ。

解答

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

A.


B.


C.
int main(){
int T; scanf("%d",&T);
while(T--){
static bool visited[110][210];
rep(i,110)rep(j,210) visited[i][j]=false;

int a,b,c; scanf("%d%d%d",&a,&b,&c);
int moneymax=100*a+b,ans=0;
for(int cnt=1;100*a+b>=c;cnt++){
if(visited[a][b]) break;
visited[a][b]=true;
b-=c; if(b<0) b+=100,a--;
swap(a,b);
if(moneymax<100*a+b) moneymax=100*a+b,ans=cnt;
}

printf("%d\n",ans);
}

return 0;
}

操作の途中で分岐することがないので、素直にシミュレートすればいい。
無限ループになるかもしれないと思って、一度訪れた状態が来たら終了するようにしたけど、必要なかったようだ。

D.


E.
int main(){
int T; scanf("%d",&T);
while(T--){
int w,h,x0,y0,L; scanf("%d%d%d%d%d",&w,&h,&x0,&y0,&L);
x0--,y0--;
int x=x0,y=y0;
static bool field[1000][1000];
rep(i,h)rep(j,w) field[i][j]=false;
field[y][x]=true;

static char cmd[1000010]; scanf("%s",cmd);
static int dir[1000010];
rep(i,L-1){
if (cmd[i]=='U') dir[i]=3;
else if(cmd[i]=='D') dir[i]=1;
else if(cmd[i]=='L') dir[i]=2;
else dir[i]=0;
x+=dx[dir[i]],y+=dy[dir[i]];
field[y][x]=true;
}

for(int i=0;;i++){
if(i<L-1){
field[y0][x0]=false;
x0+=dx[dir[i]],y0+=dy[dir[i]];
}
x+=dx[dir[L-2]],y+=dy[dir[L-2]];
if(y<0 || h<=y || x<0 || w<=x){ printf("WALL %d\n",i); break; }
if(field[y][x]){ printf("BODY %d\n",i); break; }
}
}

return 0;
}

ゲームのルールから、L ステップ目以降に蛇の進む方向は L-1 ステップ目で移動した方向。
単純にシミュレートすればいい。
L ステップ目以降は後ろの要素から順に削除していくことに注意。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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