スポンサーサイト

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

The Seventh Hunan Collegiate Programming Contest Semilive

2011/09/17 18:00~23:00 (JST)
UVa にて。

書くのを忘れていた。

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

結果

A. AC (02:29:06)
B. AC (02:51:00)
C. 2WA
D. -
E. AC (03:01:47)
F. -
G. AC (04:42:15)
H. -
I. -
J. -
K. AC (04:12:49)
Standing : 58/321


ブログに書くのが遅すぎて、どんなだったかまったく覚えてない。
1 問目を提出するのがとても遅いんだけど、何かあったんだろうか?

問題

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

A. One-Two-Three

"one", "two", "three" のどれかを高々 1 ヶ所だけ改竄した文字列が与えられる。
改竄前の文字列に対応する数字 ( 1, 2, 3 ) を答えよ。

B. Counting Game

n 人が 1, 2, ..., n-1, n, n-1, ..., 2, 1, 2, ...
の順で数を言っていく。
ただし、7 の倍数か 10 進数で書いたときに 7 が含まれる数については、発言する代わりに手を叩く。
m 番目の人が k 回目に手を叩くのはどの数か。
そのような数が存在しない場合は -1 と答えよ。

1 ≦ n, k ≦ 100

C. Polyomino Composer

n × n のグリッド上に大きい図形が、
m × m のグリッド上に小さい図形が与えられる。

小さい図形を 2 つ組み合わせて大きい図形が作れるかどうかを判定せよ。
ただし、図形の組み合わせ方は平行移動のみが許される。 ( 回転、反転はダメ )

1 ≦ n ≦ m ≦ 10

E. Box Game

2 人でターン制のゲームをする。
ゲームの状態は数の組 (a, b) で指定される。
各プレイヤーは、a, b のうち小さいほうを 0 にした後、数を任意に分配する。
この操作のあと、a, b のどちらも正整数になっていないといけない。

たとえば、(4, 3) に対しては (1, 3), (2, 2), (3, 1) の 3 通りの操作がありうる。

ゲーム開始時は (a, b) = (n, 1) とする。
先に操作ができなくなったプレイヤーの負け。

両者が最善手を尽くすとき、先手必勝かどうかを判定せよ。

2 ≦ n ≦ 109

G. Optimal Symmetric Paths

n × n のグリッドがあり、各マスに重みがついている。
左上から右下のマスへ、"右上から左下に引いた直線" に対して対称な経路で進む。
重みの和が最小になる経路は何通りあるか? mod 1,000,000,009 で。

1 ≦ n ≦ 100

K. RMQ with Shifts

サイズ n の数の配列 a[1...n] が与えられる。
次の q 個のクエリを処理せよ。

クエリ 1 : a[L...R] の最小値を求める
クエリ 2 : a[i1], a[i2], ..., a[ik] の値を左 rotate する (k ≦ 10)

1 ≦ n ≦ 100000
1 ≦ q ≦ 250000

解答

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

A.
int main(){
int T; scanf("%d",&T);
while(T--){
char s[6]; scanf("%s",s);
if(s[3]) puts("3");
else{
if(s[0]=='o' && s[1]=='n'
|| s[0]=='o' && s[2]=='e'
|| s[1]=='n' && s[2]=='e') puts("1"); else puts("2");
}
}
return 0;
}

if のれんしゅう。

B.
bool isclap(int a){
if(a%7==0) return true;
static char s[16]; sprintf(s,"%d",a);
for(int i=0;s[i];i++) if(s[i]=='7') return true;
return false;
}

int main(){
for(int n,m,k;scanf("%d%d%d",&n,&m,&k),n;){
m--;
int clap[100]={},i,p;
for(i=1;;){
for(p=0;p<n;p++,i++){
if(isclap(i)) clap[p]++;
if(p==m && clap[p]==k) goto END;
}
for(p=n-2;p>0;p--,i++){
if(isclap(i)) clap[p]++;
if(p==m && clap[p]==k) goto END;
}
}

END:
printf("%d\n",i);
}

return 0;
}

for のれんしゅう。
サイズが小さいので、普通にシミュレーションして間に合う。

C. (時間外)
void findUpperLeft(int n,char grid[10][11],int &x,int &y){
y=n;
rep(i,n) rep(j,n) if(grid[i][j]=='*') {
if(i<y || i==y && j<x) y=i, x=j;
}
}

int main(){
for(int m,n;scanf("%d%d",&m,&n),m;){
char large[10][11],small[10][11];
rep(i,m) scanf("%s",large[i]);
rep(i,n) scanf("%s",small[i]);

int lx,ly;
findUpperLeft(m,large,lx,ly);

int sx,sy;
findUpperLeft(n,small,sx,sy);

bool ok=true;
rep(i,n) rep(j,n) {
int y=i-sy+ly,x=j-sx+lx;
if(0<=y && y<m && 0<=x && x<m){
char &cl=large[y][x],&cs=small[i][j];
if (cl=='*' && cs=='*') cl='.';
else if(cl=='.' && cs=='*') ok=false;
}
else if(small[i][j]=='*') ok=false;
}

findUpperLeft(m,large,lx,ly);

rep(i,n) rep(j,n) {
int y=i-sy+ly,x=j-sx+lx;
if(0<=y && y<m && 0<=x && x<m){
char &cl=large[y][x],&cs=small[i][j];
if (cl=='*' && cs=='*') cl='.';
else if(cl=='.' && cs=='*') ok=false;
}
else if(small[i][j]=='*') ok=false;
}

rep(i,m) rep(j,m) if(large[i][j]=='*') ok=false;

puts(ok?"1":"0");
}

return 0;
}

全探索。
小さい図形の左上の点を見つけて、それを大きい図形の左上の点に合わせるということを 2 回繰り返した。
O(m2 + n2).

あほなバグを埋め込んでしまって、本番中は通らなかった。

E.
int main(){
for(int n;scanf("%d",&n),n;) puts(n&(n+1)?"Alice":"Bob");
return 0;
}

/* code for finding regularity */
/*int dp[2000][2000];bool dfs(int a,int b){ if(~dp[a][b]) return dp[a][b]; for(int i=1;i<=a/2;i++) if(!dfs(a-i,i)) return dp[a][b]=1; return dp[a][b]=0;}*/

DP して規則性を見つけた。
n が 2 のべき乗 - 1 の時だけ後手必勝。

理由は以下。

n = 1 では後手必勝。
n = 2 では先手必勝。なぜなら、相手に後手必勝の局面 ( n = 1 ) を回せるから。
n = 3 では後手必勝。なぜなら、相手に先手必勝の局面 ( n = 2 ) しか回せないから。
n = 4 では先手必勝。なぜなら、相手に後手必勝の局面 ( n = 3 ) を回せるから。
n = 5 では先手必勝。なぜなら、相手に後手必勝の局面 ( n = 3 ) を回せるから。
n = 6 では先手必勝。なぜなら、相手に後手必勝の局面 ( n = 3 ) を回せるから。
n = 7 では後手必勝。なぜなら、相手に先手必勝の局面 ( n = 4, 5, 6 ) しか回せないから。
:

同様に考えていけば、
2k, ..., 2k+1-2 は先手必勝で、2k+1-1 は後手必勝
という関係になっていることがわかる。

G.
const ll M=1000000009;

const int INF=1<<29;
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int main(){
for(int n;scanf("%d",&n),n;){
static int a[100][100];
rep(i,n) rep(j,n) scanf("%d",a[i]+j);
rep(i,n) rep(j,n-i-1) a[i][j]+=a[n-j-1][n-i-1];

static int d[100][100];
static ll cnt[100][100]; // cnt[i][j]:=(i,j)に最短経路で到達する場合の数
rep(i,n) rep(j,n) {
d[i][j]=INF;
cnt[i][j]=0;
}
d[0][0]=a[0][0];
cnt[0][0]=1;

priority_queue< pair<int,pair<int,int> > > pq;
pq.push(make_pair(-a[0][0],make_pair(0,0)));
while(!pq.empty()){
int dist=-pq.top().first;
int y=pq.top().second.first,x=pq.top().second.second;
pq.pop();

if(d[y][x]<dist || x+y==n-1) continue;

rep(i,4){
int yy=y+dy[i],xx=x+dx[i];
if(0<=yy && yy<n && 0<=xx && xx<n && x+y<n){
int nextd=dist+a[yy][xx];
if(nextd==d[yy][xx]){
cnt[yy][xx]=(cnt[yy][xx]+cnt[y][x])%M;
}
else if(nextd<d[yy][xx]){
d[yy][xx]=nextd;
cnt[yy][xx]=cnt[y][x];
pq.push(make_pair(-nextd,make_pair(yy,xx)));
}
}
}
}

int d_opt=INF;
rep(i,n) d_opt=min(d_opt,d[i][n-i-1]);

ll ans=0;
rep(i,n) if(d[i][n-i-1]==d_opt) ans=(ans+cnt[i][n-i-1])%M;
printf("%lld\n",ans);
}

return 0;
}

Dijkstra で、各マスまでの最短経路が複数あるときは、何通りあるかを覚えておけばいい。
距離を更新するのと同時に、その距離を達成する経路の個数も更新する。

斜めの直線に対して対称なパスという条件は、右下半分のパスは一意に決まるので、斜めの直線に達するまでのパスを考えるということと同じ。
( ひどい説明... )

似たような問題が AOJ にあったような気がしなくもない。

K.
const int INF=1<<29;

template<class T> struct Interval{
T a,b;
Interval(T A,T B):a(A),b(B){}
};

template<class T>
class RMQ{
int n;
vector<T> a;

void update(T v,int i,const Interval<int> &J,int u){
if(i<J.a || J.b<=i) return;
if(i==J.a && i+1==J.b){
a[u]=v;
return;
}

int m=(J.a+J.b)/2;
update(v,i,Interval<int>(J.a,m),2*u+1);
update(v,i,Interval<int>(m,J.b),2*u+2);
a[u]=min(a[2*u+1],a[2*u+2]);
}

T query(const Interval<int> &I,const Interval<int> &J,int u){
if(J.b<=I.a || I.b<=J.a) return INF;
if(I.a<=J.a && J.b<=I.b) return a[u];

int m=(J.a+J.b)/2;
T tl=query(I,Interval<int>(J.a,m),2*u+1);
T tr=query(I,Interval<int>(m,J.b),2*u+2);
return tl<tr?tl:tr;
}

public:
RMQ(const vector<T> &v):n(1){
int N=v.size();
while(n<N) n<<=1;
a=vector<T>(2*n-1);
rep(i,N) a[n+i-1]=v[i];
for(int i=n-2;i>=0;i--) a[i]=min(a[2*i+1],a[2*i+2]);
}

void update(T v,int i){
update(v,i,Interval<int>(0,n),0);
}

T query(int a,int b){
return query(Interval<int>(a,b),Interval<int>(0,n),0);
}
};

int main(){
int n,q; scanf("%d%d",&n,&q);
vector<int> a(n);
rep(i,n) scanf("%d",&a[i]);

RMQ<int> rmq(a);
while(q--){
char s[32]; scanf("%s",s);

vector<int> b;
int num=0;
for(int i=6;s[i]!=')';i++){
if(s[i]==',') b.push_back(num-1), num=0;
else num=num*10+(s[i]-'0');
}
b.push_back(num-1);

if(s[0]=='q'){
printf("%d\n",rmq.query(b[0],b[1]+1));
}
else{ // s[0]=='s'
int tmp=a[b[0]];
rep(i,(int)b.size()-1){
a[b[i]]=a[b[i+1]];
rmq.update(a[b[i+1]],b[i]);
}
a[b.back()]=tmp;
rmq.update(tmp,b.back());
}
}

return 0;
}

問題タイトルにもあるように RMQ を実装する。
rotate のクエリは、移動させる要素数が少ないので愚直にやればいい。

RMQ は Segment Tree で実装した、というかライブラリぺたり。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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