0271 Izua Dictionary
解法
この問題のポイントは、ＡＢＣＤ，，から操作した結果でありその回数が少ないという点にあります。
ＡＣＤＧ，，という単語が何番目か調べるという問題でないのです。
一回の操作で、入れ替わった結果、辞書順で何番目かを表す計算に影響するのはs～ｔまでの範囲以外変更がなくその部分だけ計算します。
((何個目の文字-左からその文字まで読んでその文字より小さい文字が左に出てくる数)*その文字より右の並びの組み合わせ数)これを各文字について足し合わせると答えが出ます。
この何個目の文字かと左から読んでその文字より小さい数が何個かは一回毎の操作で綺麗に決まるのでそこに注目してい計算します。
#include<stdio.h>
#include<string.h>
#include<iostream>
long long int bs[100001],ms[100001],mod=1000000007,perm[100001];
void calc(int n){
long long int ans=0,as[100001],cs[100001];
memcpy(as,bs,sizeof(bs));
memcpy(cs,ms,sizeof(ms));
int r,s,t;
scanf("%d",&r);
for(int i=0;i<r;i++){
scanf("%d %d",&s,&t);
s--;
t--;
long long int num=as[s];
as[s]=as[t];
as[t]=num;
int dell=0;
for(int i=0;i<s;i++){
if(as[i]<as[s])dell--;
}
cs[s]=dell;
dell=0;
for(int i=0;i<t;i++){
if(as[i]<as[t])dell--;
}
cs[t]=dell;
for(int i=s+1;i<t;i++){
if(as[s]<as[i]&&as[i]<as[t]){
cs[i]--;
}
if(as[t]<as[i]&&as[i]<as[s]){
cs[i]++;
}
}
}
for(int i=n-2;i>=0;i--){
//std::cout<<perm[n-2-i]<<" "<<i<<" "<<cs[i]<<" "<<as[i]<<"\n";
ans=(ans+(perm[n-2-i]*(as[i]+cs[i]))%mod)%mod;
}
std::cout<<ans%mod<<"\n";
}
int main(){
int n;
for(int i=0;i<=100000;i++){
bs[i]=i;
ms[i]=-i;
}
perm[0]=1;
for(long long int i=1;i<=100000;i++)perm[i]=(perm[i-1]*(i+1))%mod;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
0272 The Lonely Girl's Lie
解法
どんな勝負になっても勝てるということをいいかえると相手はこちらの手を完全に読んで一番いい手で攻めてくると想定します。
こちらの取れる一番いい手は一番レベルの高いセットで挑むことであり、相手の取る手は、それにギリギリでかてるか引き分けるカードを出すか、勝てない場合は一番弱いカードを出してくるとします。
答えを思いつくまで２時間かかりました。
#include<stdio.h>
#include<set>
#include<algorithm>
struct S{
int no,level;
bool operator<(const S& s)const{
if(level!=s.level)return level>s.level;
return no<s.no;
}
};
S as[40001];
void calc(int n){
S a,b;
std::set<S> bs;
std::set<S>::iterator it;
for(int i=0;i<n;i++){
as[i].no=i;
scanf("%d",&as[i].level);
}
for(int i=0;i<n;i++){
b.no=i+n;
scanf("%d",&b.level);
bs.insert(b);
}
std::sort(as,as+n);
int lossCount=0,k=0;
for(int i=0;i<n;i++){
a=as[i];
it=bs.lower_bound(a);
if(it!=bs.begin()&&(*it).level<a.level)it--;
b=(*it);
if(a.level<=b.level){
bs.erase(it);
lossCount++;
}else{
it=bs.end();
it--;
bs.erase(it);
}
k++;
if(k/2<(k-lossCount))break;
}
if(k==n){
printf("NA\n");
}else{
printf("%d\n",k);
}
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
問い0275 Railroad
解法
ダイクストラ法を改良して、ｂからaへ向かう最短経路のグラフを作りｂからaへ向かう経路とします。
この時駅ｂに近い駅ほど高いランクが割り当てられるようグラフの点にランクを与えておきます。
後は駅データが与えられるたびに、最短経路のグラフをｄからｃへ向かって全探索します。
探索中の駅のランクがｃよりランクが小さくなったらそれより先にｃはないので探索を打ち切ることで計算量を減らします。
色々な形のグラフを考えた時、どんなグラフでも効率的に動く手法を思いつかずこのような拙劣な方法に落ち着きました。
拙劣ですが計算量が安定するという利点があります。
私が思いついた手法で他の物はどれも、いくつかのタイプのグラフでは早く動くがあるグラフでは低速かメモリを大量に消費するという問題のあるものばかりでした。
#include<stdio.h>
#include<set>
#include<queue>
#include<map>
#include<string.h>
struct P{
int to,len,rank;
bool operator<(const P& s)const{
if(len!=s.len)return len>s.len;
return rank<s.rank;
}
};
struct Q{
int c,d;
bool operator<(const Q& q)const{
if(c!=q.c)return c<q.c;
return d<q.d;
}
};
const int size=100001;
int lenMemo[size];
int rankMemo[size];
bool isFirst[size];
std::vector<P> G[size];
std::set<int> backs[size];
bool isBackOKs[size];
bool isBackOKs2[size];
void D(int a,int b){
memset(lenMemo,-1,sizeof(lenMemo));
memset(isFirst,true,sizeof(isFirst));
memset(rankMemo,-1,sizeof(rankMemo));
std::priority_queue<P> qu;
P p,nextP;
p.len=0;
p.to=a;
p.rank=0;
qu.push(p);
lenMemo[a]=0;
while(qu.empty()==false){
p=qu.top();
qu.pop();
if(isFirst[p.to]==false)continue;
isFirst[p.to]=false;
rankMemo[p.to]=p.rank;
if(b==p.to)continue;
for(int i=0;i<G[p.to].size();i++){
nextP.to=G[p.to][i].to;
nextP.len=p.len+G[p.to][i].len;
nextP.rank=p.rank+1;
if(lenMemo[nextP.to]==-1 || lenMemo[nextP.to]>nextP.len){
lenMemo[nextP.to]=nextP.len;
backs[nextP.to].clear();
backs[nextP.to].insert(p.to);
qu.push(nextP);
}else if(lenMemo[nextP.to]==nextP.len){
backs[nextP.to].insert(p.to);
qu.push(nextP);
}
}
}
}
void saiki(int to){
if(isBackOKs[to]==false)return;
isBackOKs[to]=false;
for(std::set<int>::iterator it=backs[to].begin();it!=backs[to].end();it++){
saiki((*it));
}
}
bool search(int c,int to){
if(isBackOKs2[to]==false)return false;
isBackOKs2[to]=false;
if(c==to)return true;
if(rankMemo[c]>rankMemo[to])return false;
bool re=false;
for(std::set<int>::iterator it=backs[to].begin();it!=backs[to].end();it++){
re=re||search(c,(*it));
if(re==true) break;
}
return re;
}
int main(){
int s,r,u,v,w;
P p1;
scanf("%d %d",&s,&r);
for(int i=0;i<r;i++){
scanf("%d %d %d",&u,&v,&w);
p1.len=w;
p1.to=v;
G[u].push_back(p1);
p1.to=u;
G[v].push_back(p1);
}
int a,b,q,c,d;
scanf("%d %d %d",&a,&b,&q);
D(a,b);
memset(isBackOKs,true,sizeof(isBackOKs));
saiki(b);
for(int i=0;i<q;i++){
scanf("%d %d",&c,&d);
if(isBackOKs[c]==false&&isBackOKs[d]==false&&rankMemo[c]<rankMemo[d]){
memset(isBackOKs2,true,sizeof(isBackOKs2));
printf("%s\n",search(c,d)?"Yes":"No");
}else{
printf("No\n");
}
}
}
最終更新：2013年02月25日 14:40
