スポンサーサイト

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

Codeforces Beta Round #51

01/14 17:00~19:00 に行われた Codeforces Beta Round 51 の記録

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

あまりにできなかったので書く気がおきない。
C を安定して通せるようになりたい。

結果

A. AC(486)
B. AC(892)
C. 5WA
D. -
E. -
Hacks : 0
Standing : 208/651
Rating : 17241654


問題

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

A. Flea travel
n 個の円状に並んだクッションの上をノミが跳ね回る。
k 回目のジャンプにおいて、ノミは右回りに k-1 個のクッションを飛び越す。
与えられた n (≦1000) について、ノミがすべてのクッションの上に少なくとも 1 回乗るかどうかを判定する。

B. Smallest number
整数 a, b, c, d と二項演算 op1, op2, op3 が与えられる。
二項演算はそれぞれ加算か乗算のどちらかである。
( (a op1 b) op2 c) op3 d
において、a, b, c, d の順番を適当に並び替えて式の値を最小化せよ。

C. Pie or die
2人のプレイヤーが n × m の碁盤上でゲームをする。
あらかじめ、碁盤上には k 個のパイがある。
ゲームはターン制で行われる。

プレイヤー 1 はパイを 1 つ選んで、上下左右に 1 マスだけ動かす。
パイが盤の縁にある場合は、盤の外に出すことができる。

プレイヤー 2 は盤の縁(単位長さ)を 1 つ選んで、以降、その縁からパイを出すことができないようにする。

1 つでもパイを出すことができたらプレイヤー 1 の勝ち。そうでなければプレイヤー 2 の勝ち。
どちらも最適な戦略をとるとき、与えられた n, m, k, パイの配置 において先手必勝か後手必勝かを判定する。

D. Beautiful numbers
自然数 n が
「各桁に現れる 0 でない数は、すべて n の約数になっている」
という性質をみたすとき、n を beautiful number と呼ぶことにする。
l 以上 r 以下の beautiful number はいくつあるか?
( 1 ≦ l ≦ r ≦ 9・1018 )

E.
あとで書く。


解答

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

A.
int main(){
int n; scanf("%d",&n);
int pos=0;

vb visited(n); visited[0]=true;
rep(k,n){
pos=(pos+k)%n;
visited[pos]=true;
}

puts(count(visited.begin(),visited.end(),true)==n?"YES":"NO");

return 0;
}

n+1 回目のジャンプではちょうど一周してしまってジャンプしないことと同じ、であることに注目する。
すると、
n+2 回目のジャンプは 1 回目のジャンプと同じ。
n+3 回目のジャンプは 2 回目のジャンプと同じ。
:
ゆえに、k 回目のジャンプ後のノミの位置 x(k) は周期 n をもつ。

有限個に落としこめたので、あとはすべての場合を調べればいい。

B.
ll calc(ll a,char op,ll b){
if(op=='+') return a+b;
else return a*b;
}

ll solve(vector<ll> a,vector<char> op){
int n=a.size();
if(n==1) return a[0];

ll ans=1LL<<60;
rep(i,n)rep(j,i){
ll tmp=calc(a[i],op[0],a[j]);
vector<ll> nexta(1,tmp);
rep(k,n) if(k!=i && k!=j) nexta.pb(a[k]);
vector<char> nextop;
for(int k=1;k<op.size();k++) nextop.pb(op[k]);
ans=min(ans,solve(nexta,nextop));
}
return ans;
}

int main(){
vector<ll> a(4); rep(i,4) scanf("%I64d ",&a[i]);
vector<char> op(3); rep(i,3) scanf("%c ",&op[i]);

printf("%I64d\n",solve(a,op));

return 0;
}

問題文に書いたとおりに全パターン調べる。
再帰関数を使うとうまく書ける。

C. (時間外)
int main(){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
bool ok=false;
rep(i,k){
int x,y; scanf("%d%d",&x,&y);
if(x<=5 || n-4<=x || y<=5 || m-4<=y) ok=true;
}
puts(ok?"YES":"NO");
return 0;
}

縁に一番近い 1 つのパイにだけ注目する。
それ以外を動かすのは、プレイヤー 1 にとって損にしかならない。

縁までの距離が 4 以下であれば、プレイヤー 1 は
1. 一番近い縁まで(最短ルートで)パイを動かす。
2. 盤の縁にそってパイを動かす。
という戦術で、1周するまでに空いている縁が必ずみつかる。
なぜなら、盤の四隅にはそれぞれ 2 つの縁があるから。

縁までの距離が 5 以上であれば、プレイヤー 2 は
最初の 4 手で
1. 左上隅の縁の 1 つを塞ぐ
2. 左下隅の縁の 1 つを塞ぐ
3. 右上隅の縁の 1 つを塞ぐ
4. 右下隅の縁の 1 つを塞ぐ
としておけば、あとは縁に接したパイに対応するだけで完封できる。


解答を知ってしまえばなっとくできるけど、自力で思いつくのは難しい。
この手の問題をスマートに解ける人はすごいなぁと思う。

D. (時間外)
int gcd(int a,int b){
for(;b;swap(a,b)) a%=b;
return a;
}

int lcm(int a,int b){
return a/gcd(a,b)*b;
}

ll memo[19][48][2520];
int id_lcm[2521],dgt[19];

ll dfs(int pos,int rem,int pttn,bool flg){
if(pos==-1){ // basis case
if(rem%pttn==0) return 1;
return 0;
}

if(!flg && ~memo[pos][id_lcm[pttn]][rem]) return memo[pos][id_lcm[pttn]][rem];

ll res=0;
int endnum=(flg?dgt[pos]:9);
rep(d,endnum+1){
int nextrem=(rem*10+d)%2520;
int nextpttn=(d>0?lcm(pttn,d):pttn);
bool nextflg=(flg && d==dgt[pos]);

res+=dfs(pos-1,nextrem,nextpttn,nextflg);
}

if(!flg) memo[pos][id_lcm[pttn]][rem]=res;
return res;
}

ll solve(ll num){
int idx=0;
for(;num;num/=10) dgt[idx++]=num%10;

return dfs(idx-1,0,1,true);
}

int main(){
rep(i,19)rep(j,48)rep(k,2520) memo[i][j][k]=-1;

// precalculation: numbering of all LCM patterns
rep(i,2521) id_lcm[i]=-1;
int idx=0;
for(int i=1;i<(1<<9);i++){
int lcmnum=1;
rep(j,9) if(i&(1<<j)) lcmnum=lcm(lcmnum,j+1);
if(id_lcm[lcmnum]==-1){
id_lcm[lcmnum]=idx++;
}
} // idx==48

int t; scanf("%d",&t);
while(t--){
ll l,r; scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",solve(r)-solve(l-1));
}

return 0;
}

[ 2011/01/25 追記 ]
最初は全然わからなかったけど、yaro 氏の解説とNotOnlySuccess 氏のソースコードを併読して何とか理解した。

基本方針はメモ化再帰。
最大で 19 桁もある数を 1 つ 1 つ確かめていては全然時間が足りないので、各桁ごとに一気に数え上げてしまう。

最上位桁から始めて、下の桁に向かって DFS。
その際、入力で与えられる数を越えないように注意する。
(コード中の flg や endnum はそのためのもの)

たとえば、243 を調べるときは以下の順になる。( ? はまだ調べていない桁)
0??
 00?
  000
  001
  002
  (中略)
  009
 01?
  010
  011
  (中略)
  019
 02?
 (中略)
 09?
1??
 10?
 (中略)
 19?
2??
 20?
 (中略)
 24?
  240
  241
  242
  243


DFS の各段階において、
・今 調べている数 (下位桁は未定) と
・それまでの桁に登場した数の最小公倍数 (pttn) を引数にもっておく。
こうすることで、最下位桁まで調べ終わったとき (pos==-1) に、その数が beautiful かどうかを判定することができる。

ここまでで一応動くコードは書けるけども、このままだと TLE になる。
高速化のため、メモ化を考える。
lcm(1,2,3,4,5,6,7,8,9) = 2520 なので、DFS の過程では、今 調べている (最大で19桁にもなる) 数そのものではなく、その数を 2520 で割った余りさえ知っていれば十分。
(最下位桁まで調べ終わったときに、調べていた数が beautiful かどうかを判定できる)

この事実を使えば、
memo[調べている桁の位置][既に調べた桁の最小公倍数][調べている数 mod 2520]
   := この状態から調べていってみつかる beautiful number の個数
でメモ化できる。

E.



残りの問題は解けたら追記しよう。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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