スポンサーサイト

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

Codeforces Beta Round #87

2011/09/16 00:00~02:00 (JST)
Codeforces Beta Round #87 の参加記録

dolphinigle 回。良問。

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

結果

A. AC (00:11)
B. AC (00:28)
C. WA
D. -
E. -
Hacks : +-0 (0/0)
Standing : 123/515
Rating : 19802011


問題

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

A. Party
n 人の社員がいる。
各人には高々 1 人の直属の上司がいる。

A が B の上司であるとは、次の 2 条件のうち少なくとも一方が成立することである。
・ A が B の直属の上司である
・ A が C の上司であり、C が B の直属の上司である

A 自身が A の上司であるという状況は起こらないと仮定してよい。

社員たちを、いくつかのグループに分けたい。
ただし、各グループのどの 2 人についても、その人たちが上司-部下の関係であってはならない。
必要なグループの最小数を求めよ。

1 ≦ n ≦ 2000

B. Lawnmower
n × m のグリッドがあり、各マスは雑草が生えているか生えていないかのいずれか。

北西端のマスから出発して、すべての雑草を刈りたい。
自分は、今いるマスにある雑草のみを刈ることができる。
ただし、次の移動方法を守らないといけない。

・ 最初、自分は東を向いている。
・ 自分の向いている方向に 1 マス進むことができる。
・ 南に 1 マス進むことができる。この際、自分の向いている方向が反転する。

すべての雑草を刈るために必要な最小移動距離を求めよ。

1 ≦ n, m ≦ 150

C. Plumber
問題文中の図を参照。

n × m のグリッドがある。
各マスには 4 種類のパネルのどれかを嵌めることができる。
いくつかのマスには、最初からパネルが嵌まっているかもしれない。

パネルに書かれた線が途中で途切れない嵌め方は何通りあるか? mod 1000003 で求めよ。

1 ≦ n・m ≦ 5・105

D.

E.

解答

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

A.
int main(){
int n; scanf("%d",&n);
int p[2000],deg[2000]={};
rep(i,n){
scanf("%d",p+i);
if(~p[i]){
p[i]--;
deg[p[i]]++;
}
}

int dp[2000]={};
queue<int> qu;
rep(i,n) if(deg[i]==0) {
qu.push(i);
dp[i]=1;
}
while(!qu.empty()){
int i=qu.front(); qu.pop();
if(p[i]==-1) continue;

deg[p[i]]--;
if(deg[p[i]]==0){
qu.push(p[i]);
dp[p[i]]=max(dp[p[i]],dp[i]+1);
}
}

printf("%d\n",*max_element(dp,dp+n));

return 0;
}

各社員を頂点として、各社員からその直属の上司へ有向辺をはった有向グラフを考える。
ループがないという仮定から、有向グラフの各連結成分は木になる。 (有向なので厳密には違うけど)

サンプルの例を図に描いてみると、どうやら木の一番深い部分の深さが答えになりそう。
少なくともそれだけのグループが必要なことは自明。
逆に、それだけあれば常にグループ分けできることがわかる。
なぜなら、同じ深さにある社員を 1 つのグループにまとめるというグループ分けは問題の条件をみたすから。
( この証明は Editorials を和訳しただけ。コンテスト中には証明できなかった )

これが分かれば、あとは適当に実装すればいい。
n が小さいので O(n2) でも間に合う。

・ 根から DFS
・ すべての位置から DFS して、結果をメモ化
・ 葉から順にトポロジカル順序で調べる

などの工夫をすれば O(n) でもできる。
上記のコードは、葉から調べるアルゴリズムで実装してある。
入次数だけを見ればいいので実装は楽。

B.
int main(){
int m,n; scanf("%d%d",&m,&n);
static char grid[150][151];
rep(i,m) scanf("%s",grid[i]);

int px=0,py=0,gx=-1,gy;
static int step[150][150],mow[150][150];
rep(i,m){
int s,g,d;
if(i%2==0){ s= 0 ; g= n; d= 1; }
if(i%2==1){ s=n-1; g=-1; d=-1; }
for(int j=s;j!=g;j+=d){
if(i==0 && j==0) continue;

if(i>0 && mow[py][px]==mow[i-1][j]){
step[i][j]=step[i-1][j]+1;
}
else{
step[i][j]=step[py][px]+1;
}
if(grid[i][j]=='G'){
mow[i][j]=mow[py][px];
}
else{ // grid[i][j]=='W'
mow[i][j]=mow[py][px]+1;
gx=j;
gy=i;
}

px=j;
py=i;
}
}

printf("%d\n",~gx?step[gy][gx]:0);

return 0;
}

方向を変えることができるのは南に進むときだけであることに注意。
問題文中にある dolphingle さん作の挿絵を見るのが一番わかりやすい。

DP で解いた。

5 × 5 で例示する。
まず、以下のように動くことで必ずすべての雑草を刈ることができることがわかる。
→→→→↓
↓←←←←
→→→→↓
↓←←←←
→→→→終

このルートを全探索ルートと呼ぼう。

この順に調べていく。
dp[i][j] := マス (i, j) にいて、それまでに刈るべき雑草をすべて刈ったときの最小移動距離
とする。
全探索ルートにおける (i, j) の 1 つ前のマスを (i', j') とすると、次が成立する。
  • (i'-1, j') から (i', j') の間に雑草がないとき
    dp[i][j] = dp[i-1][j] + 1
  • (i'-1, j') から (i', j') の間に雑草があるとき
    dp[i][j] = dp[i'][j'] + 1
つまり、1 つ北にあるマスから直接降りてくるか、全探索ルートにしたがうかのいずれか。

全探索ルートにおいて最後に訪れる雑草の位置における dp 配列の値が答え。

これで最適解が求まることは、(i, j) の 1 つ前が (i', j') か (i-1, j) のどちらかしかありえないことから明らか。

以下、灰色にした部分はやりすぎ感が否めないので、読まれないほうがいいと思う。
丁寧に証明するなら、背理法を使って次のようになる。
  1. dp[0][0] から dp[i'][j'] までは最適解で、dp[i][j] で始めて最適解が得られなかったと仮定する
  2. (i, j) に至る 1 つ前の位置は、動きに関する制約から、(i', j') か (i-1, j) のどちらかしかありえない
  3. ゆえに dp[i][j] = min((i', j') での最適解, (i-1, j) での最適解) + 1 である
  4. ところが (1) の仮定から dp[i'][j'] と dp[i-1][j] は共に最適解である
  5. (4) より dp[i][j] も最適解であり、これは (1) の仮定に反する
この証明で一番重要なのは (3) で、これは部分問題の解から元の問題の解を構成できるという性質があるということ。
ものの本などでは、最適性の原理などと呼ばれている。
この性質があるから DP で最適解が得られる。

計算量は、愚直に組めば O(mn2) になるけど、少し工夫すればすぐに O(mn) に落ちる。
上記コードは O(mn)

B. (別解)
int main(){
int m,n; scanf("%d%d",&m,&n);
char g[150][151];
rep(i,m) scanf("%s",g[i]);

int ans=0,px=0,py=0;
rep(i,m) for(int j=(i%2?n-1:0);0<=j&&j<n;j+=(i%2?-1:1)) if(g[i][j]=='W') {
ans+=abs(j-px)+abs(i-py);
py=i;
px=j;
}
printf("%d\n",ans);

return 0;
}

解説を書いている間に、よりシンプルな別解を思いついたので載せておく。
詳しい解説はしないけど、難しいアイデアは使っていないので、興味がある人は (もしいれば) 読解してみてください。

キーポイントは、雑草を刈る順序は一意に定まるということ。

C. (時間外)
const int M=1000003;

int main(){
int m,n;scanf("%d%d",&m,&n);
vector< vector<char> > g(m,vector<char>(n));
rep(i,m){
scanf(" ");
rep(j,n) scanf("%c",&g[i][j]);
}

static int row[500000],col[500000];
rep(i,m) row[i]=3;
rep(j,n) col[j]=3;

rep(i,m) rep(j,n) if(g[i][j]!='.') {
int d=g[i][j]-'0';
row[i]&=1<<((d==1||d==2)^(j%2));
col[j]&=1<<((d==2||d==3)^(i%2));
}

int ans=1;
rep(i,m){
if(row[i]==0) ans=0;
if(row[i]==3) ans=2*ans%M;
}
rep(j,n){
if(col[j]==0) ans=0;
if(col[j]==3) ans=2*ans%M;
}
printf("%d\n",ans);

return 0;
}

この問題は特におもしろかったので、はりきって図を描いてみた。

5 × 8 の例で説明する。
たとえば、1 つの解として

のようなものがある。
このまま見ていてもよくわからない。

縦の線にだけ注目してみる。すると次のようになる。

非常に明快なパターンがあることがわかる。
つまり、各列についてちょうど 2 通りの埋め方がありうる。

今度は横の線にだけ注目してみる。すると次のようになる。

これについても同様に、各行についてちょうど 2 通りの埋め方がありうる。

しかも、行のパターンと列のパターンはまったく独立に決めることができる。

なので、最初にどのマスにもパネルが嵌まっていなければ、可能な嵌め方の総数は 2m+n 個になる。

最初からいくつかのマスにパネルが嵌まっている場合には、いくつかの行・列は 0 or 1 通りの決め方しかなくなる。
結局、答えは 2 のべき乗の形になる。

計算量は O(mn)。

D.


E.


感想

赤くなった。
でも、自分の実力が Rating に見合っていないことは自分が一番わかっているので、もっともっと練習して強くなりたい。

今回から、アルゴリズムの正しさの証明と、(時間) 計算量の評価をしっかりやることにする。
言うまでもなく基礎が一番大事だし、ひっかけのある問題の対策としてもこれはいい方法だと思う。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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