Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2132-90812800
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #92 DIV1 C問題/DIV2 E問題 - Brackets (この記事を編集する[管理者用])

Source

Codeforces Beta Round #92 DIV1 C問題 (1500pt)
Codeforces Beta Round #92 DIV2 E問題 (2500pt)
Problem description

問題概要

サイズn*m (100*100以下) の2次元のグリッドを考える.
各セルに(か)を書く.
左上から,右か下にしか移動せずに,右下までたどり着くとき,すべてのパスに対してカッコがうまく対応付くようになっていなければならない.
条件を満たすカッコの書き方について,以下の方法でソートする.
 各セルに異なる優先順位が与えられる.
 各書き方について,優先順位の高いセルから順に見て行って,最初に異なる場所を発見したら,その場所に(が書かれている方が先に来る.
サイズと優先順位が与えられた時,その方法でソートしたとしてk番目 (10^18以下) の書き方を求める問題.

解法

まず,右上から左下にかけての斜めのラインは全て同じ記号を入れなくてはいけない.
なので,1次元の問題になる.
優先順位の高いセルから順番に確定していく.
ある部分を確定した時のカッコの書き方の数はDPで求めることができる.
愚直に書いても,O( (n+m)^3 )程度でできる.
DPするとき,パターンの数はlong longでオーバーフローするので,kを超えたらk+1と見なすなど適当な処理をする.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define LIM 1100000000000000000LL

ll dp[300][300];
int len;
char res[300];

ll solve(int st, int depth){
  int i,j,k;
  ll ret = 0;

  if(dp[st][depth] >= 0) return dp[st][depth];
  
  if(st==len){
    if(depth==0) ret++;
    return dp[st][depth] = ret;
  }

  if(res[st]==0 || res[st]=='(') ret += solve(st+1, depth+1);
  if(depth && (res[st]==0 || res[st]==')')) ret += solve(st+1, depth-1);

  if(ret > LIM) ret = LIM;

  return dp[st][depth] = ret;
}

int main(){
  int i,j,l,m,n;
  int x, y;
  int p[300];
  ll k, tmp;

  while(scanf("%d%d%I64d",&x,&y,&k)==3){
    len = x+y-1; k--;
    rep(i,len) p[i] = 1000000000;
    rep(i,len) res[i] = 0;

    rep(i,x) rep(j,y){
      scanf("%d",&m);
      if(p[i+j] > m) p[i+j] = m;
    }

    for(;;){
      rep(i,len+2) rep(j,len+2) dp[i][j] = -1;
      
      m = 1000000000;
      rep(i,len) if(m > p[i]) m = p[i];
      if(m==1000000000) break;
      
      rep(i,len) if(m==p[i]) break;
      p[i] = 1000000000;
      res[i] = '(';
      tmp = solve(0,0);
      if(tmp <= k){
        k -= tmp;
        res[i] = ')';
      }
    }

    rep(i,x){
      rep(j,y) putchar(res[i+j]);
      puts("");
    }
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2132-90812800
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。