問い1500 ID
解法
#include<stdio.h>
#include<string.h>
char id[100001];
int memo[100001][10];
int main(){
int n,m,a;
int base2[10]={0,2,4,6,8,1,3,5,7,9};
bool oks[10]={0,0,0,0,0,0,0,0,0,0};
scanf("%d %s",&n,id);
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d",&a);
oks[a]=true;
}
memset(memo,0,sizeof(memo));
memo[0][0]=1;
for(int i=1;i<=n;i++){
char c=id[n-i];
if(c=='*'){
for(int j=0;j<=9;j++){
for(int k=0;k<=9;k++){
if(oks[k]==true){
if(i%2==0)memo[i][(j+base2[k])%10]+=memo[i-1][j];
else memo[i][(j+k)%10]+=memo[i-1][j];
}
}
}
}else{
for(int j=0;j<=9;j++){
if(i%2==0)memo[i][(j+base2[c-'0'])%10]+=memo[i-1][j];
else memo[i][(j+(c-'0'))%10]+=memo[i-1][j];
}
}
}
printf("%d\n",memo[n][0]);
}
1501 Grid
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
struct S{
int r,c,len;
bool operator<(const S& s)const{
return len<s.len;
}
};
int rootMemo[1002][1002];
int mod=100000007;
int calc(int r,int c){
memset(rootMemo,0,sizeof(rootMemo));
rootMemo[0][1]=1;
for(int i=1;i<=r+1;i++){
for(int j=1;j<=c+1;j++){
rootMemo[i][j]=rootMemo[i-1][j]+rootMemo[i][j-1];
if(rootMemo[i][j]>mod)rootMemo[i][j]-=mod;
}
}
return rootMemo[r+1][c+1];
}
int main(){
S s[9];
int r,c,ys,xs,yg,xg,no;
scanf("%d %d %d %d %d %d",&r,&c,&ys,&xs,&yg,&xg);
xs++;
ys++;
xg++;
yg++;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
no=i*3+j;
s[no].r=abs((ys+r)-(yg+r*i));
s[no].c=abs((xs+c)-(xg+c*j));
s[no].len=s[no].r+s[no].c;
}
}
std::sort(s,s+9);
int limit=s[0].len;
int ans=0;
for(int i=0;i<9;i++){
if(s[i].len>limit)break;
ans=(ans+calc(s[i].r,s[i].c))%mod;
}
printf("%d\n",ans);
}
1502 War
解法
遠くへいける兵士から優先して動かします。
第一陣の4人は先ず上下左右4方向へまっすぐ。
第二陣の4人は、一列ずれたところ1陣と平行にまっすぐ。
以下第n陣はn列ずれたところをまっすぐ進み全部いなくなるまでこれを続けるだけです。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
int main(){
std::vector<long long int> v;
long long int n,a,ans=1;
std::cin>>n;
while(n--){
std::cin>>a;
v.push_back(a);
}
std::sort(v.rbegin(),v.rend());
for(int i=0;i<v.size();i++){
ans+=v[i]-i/4>0?v[i]-i/4:0;
}
std::cout<<ans<<"\n";
}
1505
解法
この問題は苦労しました。
多分もっと賢い方法があると思いますが私は以下の小手先テクニックでクリアしました。
まず全ての部屋でスタート地点とゴール地点までの距離をダイクストラ法で計算、スタートからの距離をx軸、ゴールからの距離をy軸として部屋の位置を平面上にプロットしていきます。
すると、問い合わせがあったのより左上にある点の数を数える問題に問題が簡素化されます。
次に部屋をy軸を優先してソートしたものを用意しy軸優先のソートには問い合わせの点も入れておきます。
y軸を優先してソートしたものを順番に空のx軸優先でソートして代入する集合に追加していきます。
問い合わせがあった場合x軸優先のソートから何個目までが問い合わせの点より左上にあるかを数えます。
これだけではx軸に入れていく作業が遅くなり速度が出ません。
これを回避するために、x軸の集合を細かく切り分けています。
#include<stdio.h>
#include<queue>
#include<map>
#include<vector>
#include<list>
#include<string.h>
#include<iostream>
#include<algorithm>
long long int memo[100001];
struct road{
int nextRoom;
long long int len;
};
struct S{
long long int len;
int roomNo;
bool operator<(const S& s)const{
if(len!=s.len)return len>s.len;
return roomNo<s.roomNo;
}
};
struct Room{
long long int sx,gy;
bool isRoom;
int no;
bool operator==(const Room& r)const{
return sx==r.sx&&gy==r.gy&&isRoom==r.isRoom&&no==r.no;
}
};
class GYSorter {
public:
//足し算用
bool operator()(const Room& l, const Room& r) const {
if(l.gy!=r.gy) return l.gy>r.gy;
if(l.sx!=r.sx) return l.sx<r.sx;
if(l.isRoom!=r.isRoom)return l.isRoom>r.isRoom;
return l.no<r.no;
}
};
class SXSorter {
public:
bool operator()(const Room& l, const Room& r) const {
if(l.sx!=r.sx) return l.sx<r.sx;
if(l.gy!=r.gy) return l.gy>r.gy;
if(l.isRoom!=r.isRoom)return l.isRoom>r.isRoom;
return l.no<r.no;
}
};
bool gyHikaku(const Room& l, const Room& r){
if(l.gy!=r.gy) return l.gy>r.gy;
if(l.sx!=r.sx) return l.sx<r.sx;
return false;
}
std::map<int,std::vector<road> > G;
Room rooms[100001];
void D(int roomNo, int n, bool isCalcX){
memset(memo,-1,sizeof(memo));
S s,nextS;
s.roomNo=roomNo;
s.len=0;
std::priority_queue<S> qu;
qu.push(s);
while(qu.empty()==false){
s=qu.top();
qu.pop();
if(memo[s.roomNo]!=-1&&memo[s.roomNo]<=s.len)continue;
memo[s.roomNo]=s.len;
for(int i=0;i<G[s.roomNo].size();i++){
nextS.roomNo=G[s.roomNo][i].nextRoom;
nextS.len=s.len+G[s.roomNo][i].len;
if(memo[nextS.roomNo]!=-1&&memo[nextS.roomNo]<=nextS.len)continue;
qu.push(nextS);
}
}
for(int i=0;i<n;i++){
rooms[i].isRoom=true;
rooms[i].no=i;
if(isCalcX==true) rooms[i].sx=memo[i];
else rooms[i].gy=memo[i];
}
}
std::vector<Room> qs,qs2,sortSx,sortGy,sortSx2[250];
int main(){
int n,m,a,b;
road r;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
std::cin>>a>>b>>r.len;
r.nextRoom=b;
G[a].push_back(r);
r.nextRoom=a;
G[b].push_back(r);
}
D(0,n,true);
D(n-1,n,false);
std::vector<Room>::iterator vIt;
std::map<Room,int,GYSorter> anser;
Room room,room2;
for(int i=0;i<n;i++){
sortGy.push_back(rooms[i]);
sortSx.push_back(rooms[i]);
}
int q;
scanf("%d",&q);
for(int i=0;i<q;i++){
room.isRoom=false;
room.no=n+i;
std::cin>>room.sx>>room.gy;
sortGy.push_back(room);
qs2.push_back(room);
}
std::sort(sortGy.begin(),sortGy.end(),GYSorter());
std::sort(sortSx.begin(),sortSx.end(),SXSorter());
int left=0;
int count=0;
for(int i=0;i<sortGy.size();i++,count++){
room=sortGy[i];
int no=count/1000;
if(room.isRoom==true){
vIt=std::upper_bound(sortSx2[no].begin(),sortSx2[no].end(),room,SXSorter());
sortSx2[no].insert(vIt,room);
}else{
int sum=0;
for(int i=0;i<=no;i++){
if(sortSx2[i].size()>0){
vIt=std::lower_bound(sortSx2[i].begin(),sortSx2[i].end(),room,SXSorter());
sum+=std::distance(sortSx2[i].begin(),vIt);
}
}
anser[room]=sum;
}
}
for(int i=0;i<q;i++){
std::cout<<anser[qs2[i]]<<"\n";
}
}
2013/3/21
AOJ 1507 Dungeon (II)
解法
難しい問題です。
部屋iから部屋jへ移動するときのコストを求める関数をf(i,j)とするとこの関数が計算量1だったとしても200億回の計算が必要になります。
この手法ではコード実行時間が長くなりすぎて、問題で要請されている2秒以内の計算時間で答えをだせません。
なので上手にまとめて計算する工夫が必要になります。
この問題の解法のこつは、全てのi~jへの移動を行ったときの経路を考えるとき。
ある通路がある経路の最大値であるとは何かを考えることです。
一度全ての通路を切断して短い通路から繋げなおしていきます。
ある通路を繋げた時、その時点のつながりから
繋げた通路の片方の先にある部屋の数*もう片方の先にある部屋の数*その通路の距離
という式がその通路がその経路のコストになる条件を満たす経路達のコストの合計となります。
後はユニオン木もどきで高速化して片が付きます。
もっと速度が落ちるかと思ったらコード実行速度2位でした。
AOJの難問にしては珍しく正答者のコード実行速度のばらつきが少ないです。
皆のコードが同じタイムであることを考えると皆同じような考え方で解いたと思われます。
色々なかたが自分の考えた独自解法で解いた結果コード実行速度がばらつくのがAOJの特徴ですが、この問題は色々な解法がなかったようです。。
#include<stdio.h>
#include<iostream>
#include<queue>
struct Way2{
int a,b;
long long int cost;
bool operator<(const Way2& w)const{
return cost>w.cost;
}
};
const int size=200*1000+1;
long long int roomCount[size]={0};
int tree[size];
std::priority_queue<Way2> qu;
int saiki(int now,int newTop){
int re;
if(now==tree[now]){
re=roomCount[now];
}else{
re=saiki(tree[now],newTop);
}
tree[now]=newTop;
return re;
}
int main(){
int n,a,b,c;
long long int ans=0,sum=0,t1,t2;
Way2 w2;
scanf("%d",&n);
for(int i=0;i<n-1;i++){
scanf("%d %d %d",&a,&b,&c);
if(a<b){
w2.a=a;
w2.b=b;
}else{
w2.a=b;
w2.b=a;
}
w2.cost=c;
qu.push(w2);
}
for(int i=0;i<=n;i++){
tree[i]=i;
roomCount[i]=1;
}
while(qu.empty()==false){
w2=qu.top();
qu.pop();
t1=saiki(w2.a,w2.a);
t2=saiki(w2.b,w2.a);
roomCount[w2.a]=t1+t2;
ans+=t1*t2*w2.cost;
}
std::cout<<ans<<"\n";
}
AOJ 1509 Rental DVD Shop NEO
#include<stdio.h>
int main(){
int a,b,c,d,e;
int na,nb,nc,ans,ans2,t;
while(1){
scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
if(a+b+c+d+e==0)break;
scanf("%d %d %d",&na,&nb,&nc);
ans2=a*na+b*nb+c*nc;
if(nc>=d){
ans=a*na+b*nb+e*nc;
}else if(nc+nb>=d){
t=nc+nb-d;
ans=a*na+b*t+d*e;
}else if(nc+nb+na>=d){
t=nc+nb+na-d;
ans=a*t+e*d;
}else if(nc*c>=d*e){
ans=a*na+b*nb+d*e;
}else if(nc*c+nb*b>=d*e){
ans=a*na+d*e;
}else if(nc*c+nb*b+na*a>=d*e){
ans=d*e;
}else{
ans=ans2;
}
ans=ans<ans2?ans:ans2;
printf("%d\n",ans);
}
}
最終更新:2013年05月01日 11:51