Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #28 B問題 - pSort (この記事を編集する[管理者用])

Source

Codeforces Beta Round #28 B問題
Problem description
Beta Round #28の自分の参加記録

問題概要

最初,n個の箱に順番に1~nまでの数字が入っている.
 k個目の箱に入ってる数字をd[k]個だけ離れた箱の数字と取り替える
という操作を無限回までできる.
与えられた状態に移動できるかどうかを判定する問題.
nは100以下.

解法

数字別に見てあげて,すべての数字が目的地に辿りつけるなら,全部の数字が同時に辿りつける.
nが小さいのでワーシャルフロイドすれば良い.(n回DFSでもOK)

C言語のスパゲッティなコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n;
  int edge[120][120];
  int go[120];

  scanf("%d",&n);
  rep(i,n) scanf("%d",go+i), go[i]--;
  rep(i,n) rep(j,n) edge[i][j]=0; rep(i,n) edge[i][i]=1;
  rep(i,n){
    scanf("%d",&k);
    if(i-k >= 0) edge[i][i-k]=edge[i-k][i]=1;
    if(i+k <  n) edge[i][i+k]=edge[i+k][i]=1;
  }
  rep(k,n) rep(i,n) rep(j,n) edge[i][j] |= (edge[i][k]&edge[k][j]);

  rep(i,n) if(!edge[i][go[i]]) break;
  if(i==n) puts("YES"); else puts("NO");

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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