堀江 伸一
〒675-0033-79-16
2013/5/30
return (((a^b)+2*(a&b))==(a-~b-1))*(2*(a|b)-(a^b));
このコードはなんだろう？
答え
ずっと前に私が書いたa+bを行うコード。
数式を考えてるときは結構楽しかった。
ナンセンスマシーンを作る人の楽しみを少しだけ味わった。
上のコードは数式上は完全に正しいが完全にナンセンスである。
清く正しいコードは
return a+b;
である。
2013/3/21
条件
最大２０万部屋(n部屋)あるダンジョンがｎ-1本の通路でつながっている。
どの部屋からスタートしても他の部屋を経由してすべての部屋にいくことが出来る。
部屋には番号が振られており,1,,,nまで重複なく振られている。
i<ｊとなる部屋i～部屋jへの移動を考える。
移動したとき、途中で通路の長さが最大になる通路を通るが、この通路の長さを部屋i～部屋jへの移動にかかるコストと定義しこれを最小化することを考える。
部屋のつながりと通路の距離のデータが与えられるので全てのi～jの移動による、コストの合計を答えよ。
解法
難しい問題です。
部屋iから部屋jへ移動するときのコストを求める関数をf(i,j)とするとこの関数が計算量１だったとしても２００億回の計算が必要になります。
この手法ではコード実行時間が長くなりすぎて、問題で要請されている２秒以内の計算時間で答えをだせません。
なので上手にまとめて計算する工夫が必要になります。
この問題の解法のこつは、全てのi～jへの移動を行ったときの経路を考えるとき。
ある通路がある経路の最大値であるとは何かを考えることです。
一度全ての通路を切断して短い通路から繋げなおしていきます。
ある通路を繋げた時、その時点のつながりから
繋げた通路の片方の先にある部屋の数*もう片方の先にある部屋の数*その通路の距離
という式がその通路がその経路のコストになる条件を満たす経路達のコストの合計となります。
後はユニオン木もどきで高速化して片が付きます。
もっと速度が落ちるかと思ったらコード実行速度２位でした。
ＡＯＪの難問にしては珍しく正答者のコード実行速度のばらつきが少ないです。
皆のコードが同じタイムであることを考えると皆同じような考え方で解いたと思われます。
色々なかたが自分の考えた独自解法で解いた結果コード実行速度がばらつくのがＡＯＪの特徴ですが、この問題は色々な解法がなかったようです。
#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";
}
2013/3/22
これ難しいなあ。
どの道を何回通ったかと今いるポイントと今のタイムを基準に点を決めてグラフに翻訳すると点の数が物凄いことになるので単純なグラフで解いてはいけない。
1→３→１→２→1→３→１→２→１は
1→２→１→２→１と１→３→１→３→１に分解できる。
ということを利用して解けばいいんだろうけど。
正答者数を考えた時世間ではそんなに難しい問題に分類されてないはずなので色々考えてみます、、、
ここで気になる点は、グラフは木構造だという点です。
ある枝先を何回も往復して散歩した時、その枝先は一度で集中的に回り、回り終えたら２度と入らないと道を削除します。
これなら枝先を何回通ったかの情報がいらずタイムと得られた価値の組み合わせだけが必要な情報として手に入ります。
これを利用して解けそうなのですが、これを綺麗に処理する処理手順の順序集合が見えません。
一応上記考えでコードを書いてみましたが。
駄目でした。
18個目あたりのジャッジデータでタイムリミッドくらいます。
そらまあ最悪の計算量が２５００万*300=75億回.
普通のコードならちょっと遅いねで済みますが、競技プログラムでは遅いではすみません。
通るわけがないのですが今のところこれより賢い方法を思いつかない状態です。
これはいい考えを思いつくまで一度諦めた方がいいかも。
この問題は１から出発して木を精査していくことで解けました。
親猫を1に置き探索猫をどれかの道に向かわせます。
探索猫は辿りついた場所が枝先でないなら親猫となってこの広場に居座ります。
親猫は探索猫を一匹作り、道の先に向かわせこれを連鎖させます。
枝先にたどり着いたらその広場に入る道を往復した結果得られる価値と距離の対応表を親猫に返します。
親猫は探索猫が持ち帰った対応表を使って自分の持ってる価値と距離の対応表をより良い結果に更新します。
調べてない道がまだ残ってるなら、親猫は自分の対応表を持たせて探索猫をその道に向かわせ上記と同じ作業を繰り返します。
親猫は全ての道を探索猫に探索させ終わったら自分の得た対応表を親猫に返します。
この時、自分の通った道を何度か往復した場合を考慮に入れた対応表を親猫に返せば答えとなります。
2013/3/27
https://www.youtube.com/watch?v=ZoZ0ZAzr6eg
こういう動画を見ると恥ずかしくて死にたくなるな。
自分がやってるＡＯＪの問題は、種が分かれば後は簡単に解けることが多い問題が多い。
正答者数２０人近辺かそれ以下の難問を自力で解いても、計算量が多くなると言ってもたかが知れているんだよな。
短時間でぱぱっと解かれることを想定してるから種一つ分かれば後は実装ゲー中心。
リンク先動画みたいに大量の砂粒のシミュレーションをする計算とか。
どこからこんな大量の計算量をＣＰＵから見つけ出してくるんだろうかと疑問になる。
こういう動画を見ると大学いっとけばよかったなと思ったり。
動画見てると表面的に浅くしか数学や物理を理解してない自分という現実が迫ってくるわけだ。
ＡＯＪの難問と言っても基本的に素朴に当たり前に言えることを探しだして、それを基底に処理手順の順序集合を決定してるだけだしな。
基本私の考えは底が浅い。
Ｗｉｋｉで数学の話なんか読むとどれだけ奥が深いのこの話、という気分になるし。
世間がロケット作ってるのを横目に私はおもちゃの花火作ってる気分になる、、、
2013/4/2
2013/4/10
ＡＯＪ0575に挑戦。
解法
とりあえず距離はダイクストラ法で求めるところまでは簡単。
問題はその先。
問題を展開してデータ処理手順に順序集合が適用できるよう組み立ててみたら何か間違ってたらしい、、、
何故か判らないが採点データ5で答えが一つだけあわない、、、
どうなってんだろ？
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<string.h>
#include<stdlib.h>
#include<stack>
struct E{
int no,len;
bool operator<(const E& e)const{
return len<e.len;
}
};
struct DE{
int no,len;
bool operator<(const DE& e)const{
return len>e.len;
}
};
struct Q{
int from,to;
bool operator<(const Q& q)const{
if(from!=q.from)return from<q.from;
return to<q.to;
}
};
std::vector<E> G[100001];
E memos[100001];
std::vector<int> qsList[100001],nowQs[100001];
std::vector<Q> qs;
std::map<Q,int> ans;
int cityNoToOrderNo[100001];
std::map<int,int> orderNoToMinLen;
std::map<int,std::vector<int> > minLenToCityList;
bool spents[100001];
void d(int n){
//ダイクストラ
int lens[100001];
memset(lens,-1,sizeof(lens));
std::priority_queue<DE> pQ;
DE e,e2;
for(int i=0;i<G[0].size();i++){
e.no=G[0][i].no;
e.len=0;
pQ.push(e);
}
lens[0]=0;
while(!pQ.empty()){
e=pQ.top();
pQ.pop();
if(lens[e.no]!=-1&&e.len>=lens[e.no])continue;
lens[e.no]=e.len;
for(int i=0;i<G[e.no].size();i++){
e2.no=G[e.no][i].no;
e2.len=G[e.no][i].len+e.len;
if(lens[e2.no]==-1||(lens[e2.no]>e2.len)){
pQ.push(e2);
}
}
}
//for(int i=0;i<=n;i++)printf("%d , ",lens[i]);
for(int i=1;i<=n;i++){
memos[i].no=i;
memos[i].len=lens[i];
}
}
int main(){
int n,m,k,q,a,b;
scanf("%d %d %d %d",&n,&m,&k,&q);
E e;
for(int i=0;i<m;i++){
scanf("%d %d %d",&a,&b,&e.len);
e.no=b;
G[a].push_back(e);
e.no=a;
G[b].push_back(e);
}
//街0という架空の町を作り祭りがおこなわれているのは全部この町と距離0でつながってるとする
//これにより祭りの距離は街0からの距離という問題に置き換えることが出来る
for(int i=0;i<k;i++){
scanf("%d",&a);
e.no=a;
e.len=0;
G[0].push_back(e);
}
d(n);
int from,to;
Q q1;
for(int i=0;i<q;i++){
scanf("%d %d",&from,&to);
q1.from=from;
q1.to=to;
qs.push_back(q1);
qsList[from].push_back(to);
qsList[to].push_back(from);
}
for(int i=0;i<qs.size();i++){
ans[qs[i]]=0;//とりあえずダミーデータを入れておく
}
std::priority_queue<E> qu;
E e1=memos[0],e2;
for(int i=1;i<=n;i++){
if(memos[i].len>e1.len){
e1=memos[i];
}
}
if(e1.len>0){
qu.push(e1);
spents[e1.no]=true;
}
int no=0;
std::map<int,std::vector<int> >::iterator it;
std::vector<int>::iterator itV;
std::vector<int> v;
std::map<int,int>::iterator it2;
memset(cityNoToOrderNo,-1,sizeof(cityNoToOrderNo));
memset(spents,false,sizeof(spents));
while(qu.empty()==false){
e1=qu.top();
qu.pop();
for(it=minLenToCityList.lower_bound(e1.len);it!=minLenToCityList.end();it++){
for(itV=(*it).second.begin();itV!=(*it).second.end();itV++){
orderNoToMinLen.erase((*itV));
}
}
minLenToCityList.erase(minLenToCityList.lower_bound(e1.len),minLenToCityList.end());
cityNoToOrderNo[e1.no]=no;
orderNoToMinLen[no]=e1.len;
minLenToCityList[e1.len].push_back(no);
for(int i=0;i<qsList[e1.no].size();i++){
int to=qsList[e1.no][i];
nowQs[to].push_back(e1.no);
}
for(int i=0;i<nowQs[e1.no].size();i++){
int to=nowQs[e1.no][i];
int oNo=cityNoToOrderNo[to];
it2=orderNoToMinLen.lower_bound(oNo);
int tempLen=(*it2).second;
q1.from=e1.no;
q1.to=to;
ans[q1]=tempLen;
q1.from=to;
q1.to=e1.no;
ans[q1]=tempLen;
/*if(q1.from==3495&&q1.to==4398){
printf("\nlen=%d cNo=%d to=%d no=%d oNo=%d\n",e1.len,e1.no,to,no,oNo);
for(it2=orderNoToMinLen.begin();it2!=orderNoToMinLen.end();it2++){
printf("<%d %d>",(*it2).first,(*it2).second);
}
printf("\n");
}*/
}
for(int i=0;i<G[e1.no].size();i++){
e2.no=G[e1.no][i].no;
e2.len=memos[e2.no].len;
if(spents[e2.no]==true)continue;
spents[e2.no]=true;
qu.push(e2);
}
no++;
}
for(int i=0;i<qs.size();i++){
printf("%d\n",ans[qs[i]]);
}
/*
FILE *fp; //(1)ファイルポインタの宣言
if ((fp = fopen("smpl.txt", "w")) == NULL) {
printf("file open error!!\n");
exit(EXIT_FAILURE); // (3)エラーの場合は通常、異常終了する
}
for(int i=0;i<qs.size();i++){
fprintf(fp,"%d %d %d\n",qs[i].from,qs[i].to,ans[qs[i]]);
}
fclose(fp);
*/
}
2013/5/6
2013/5/10
2チャンネルで、アンパンマンを親子で見に言ったら親の私が泣いてしまったスレが共感を呼んで盛り上がったりしてるところを考えると。
2ちゃんも結構既婚者多いのかなとか思ったりする今日この頃。
2013/5/14
最終更新：2013年05月31日 17:12
