C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[9]: プログラムの練習問題でわからないことが

分類:[C/C++]　

2011/10/21(Fri) 15:52:32 編集(投稿者)
2011/10/21(Fri) 15:52:28 編集(投稿者)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
勉強のためにリンク先問題をとこうとしているのですがなかなか解けずに困っております。
どなたかアドバイスをいただけないでしょうか？

一応答えがあり模範解答的な考え方はこちらです。
http://www.ioi-jp.org/joi/2005/2006-ho-prob_and_sol/2006-ho-t5-review.html
集合とか苦手なので良く分からなず模範解答を手本にためしに手探りで下記コードを書いたのですが、コード実行速度が遅すぎるというので不正解となってしまいます。
公開されているジャッジデータで試すとコード自体は正しい答えを出しているので問題になるのは速度だけなのですが。
模範解答の考え方の解説かコードの高速化の指摘を頂けたらと思います。

#include<stdio.h>
#include<map>
#include<vector>
struct col{
//短冊に切ったシートのY座標上下
int y1,y2;
};

void calcR(int& ansR,int& ansS,std::vector<col>& tate,std::map<int,int>& sheetIO) {
//X列にあるシートの周長と面積を求める
col t;
std::map<int,int>::iterator it;
tate.clear();
it=sheetIO.begin();
t.y1=(*it).first;
int inOutCount=0;
while(it!=sheetIO.end()){
inOutCount+=(*it).second;
if(inOutCount==0){
t.y2=(*it).first;
ansR+=(t.y2-t.y1)*2+2;//Y軸と平行に短冊に切ったシートの上下左右の周長
ansS+=t.y2-t.y1;//面積
tate.push_back(t);
it++;
if(it==sheetIO.end())break;
t.y1=(*it).first;
}else{
it++;
}
}
}
void setMap(int n,int type){
std::map<int,int> sheetIO[10002];//シートにsheetIO[x座標]。シートに入る出るの管理をするY座標は０から増えていく
std::map<int,int> tempIO;
int ioCount;
int x1,y1,x2,y2,x,y;
int maxX=0,minX=10001;
std::map<int,int>::iterator it;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++;//0列目はダミーとして使うので一列シートをずらす
x2++;
if(x1<minX)minX=x1;
if(x2>maxX)maxX=x2;
//シートを短冊状に切ってマップ上に重ねていく、
//ｘ座標を固定してY＝０からY=10000までシートに入る出るをカウントしていく
for(int x=x1;x<x2;x++){
if(sheetIO[x].find(y1)==sheetIO[x].end()){

sheetIO[x][y1]=1;
}else{
//シートが2枚以上重なった地点にはいるY座標
sheetIO[x][y1]++;
}
if(sheetIO[x].find(y2)==sheetIO[x].end()){
sheetIO[x][y2]=-1;
}else{
//シートから抜け出す地点
sheetIO[x][y2]--;
}
}
if(i>0 && i%50==0){
//シートに入った出たの量が多くなるのでここで整理する
//シートを短冊状にきってあるので一列のシートと見て重複部分を統合する。
for(int x=minX;x<=maxX;x++){
it=sheetIO[x].begin();
if(it==sheetIO[x].end())continue;
ioCount=0;
tempIO.clear();
tempIO[(*it).first]=1;
while(it!=sheetIO[x].end()){
ioCount+=(*it).second;
if(ioCount==0){
//シートに入った数と出た数が同じつまりシートから出た
tempIO[(*it).first]=-1;
it++;
if(it==sheetIO[x].end())break;
tempIO[(*it).first]=1;
}else{
it++;
}
}
//データ更新
sheetIO[x].clear();
sheetIO[x].insert(tempIO.begin(),tempIO.end());
}
}
}
int ansR=0,ansS=0,old,now,p1,p2;//周長
std::vector<col> tate[2];
int yOld1,yOld2,yNow1,yNow2;
//ここから先周長と面積を計算する。
for(int x=minX;x<=maxX;x++){
calcR(ansR,ansS,tate[x%2],sheetIO[x]);
old=(x+1)%2;
now=x%2;
p1=p2=0;
//一列ごとにシートのしかれた部分に出る入るを元に面積と周長を計算する。
while(p2<tate[now].size() && p1<tate[old].size()){
yOld1=tate[old][p1].y1;
yOld2=tate[old][p1].y2;
yNow1=tate[now][p2].y1;
yNow2=tate[now][p2].y2;
//隣の列Oldと今計算中の列nowでシートが接する部分があればそれを周長からひく。
if(yOld1>=yNow2){
p2++;
}else if(yOld2<=yNow1){
p1++;
}else if(yOld2>=yNow2 && yOld1>=yNow1 && yOld1<=yNow2){
ansR-=2*(yNow2-yOld1);
p2++;
}else if(yOld2>=yNow2 && yOld1<=yNow1){
ansR-=2*(yNow2-yNow1);
p2++;
}else if(yOld2<=yNow2 && yOld1<=yNow1 && yOld2>=yNow1){
ansR-=2*(yOld2-yNow1);
p1++;
}else if(yOld2<=yNow2 && yOld1>=yNow1){
ansR-=2*(yOld2-yOld1);
p1++;
}
}
}
//答えの出力
if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}

質問2
同じ問題をBitSetで解こうと考え下記のようなコードを書いてみました。
平面を升目で区切り、シートのある部分を１ない部分を０とし１Bit単位で管理しているコードです。
残念ながら低速なコードなのですが一つ問題に当たりました。

コードを実行し問題付属のサンプルInputを入力していただくと、シートのあるなしデータをマップで表示し行の最後にCount関数で求めた行にある１の数を出しています。
周長と面積を計算して表示するのですが、計算に使うBitSetのCount関数が予測と違う値を返すのです。

BCCでコンパイルしているのですが表示したマップの各行にある１の数とCount関数で出てくる１の数が合わい。

これはどういうことでしょうか？
Bit演算に関しては私はまだ初心者レベル幼稚園児が砂場で遊んでいるレベルです。
よく分かってないことも多いのでどなたかアドバイスを頂けたらと思います。
なぜtemp.countとstd::cout<<tempで表示した１の数が一致しないのでしょうか？

#include<stdio.h>
#include <bitset>
#include <iostream>
const int size=13;//縦横のマップサイズとりあえずサンプルデータを試せるサイズに限定
std::bitset<size> map[size],temp,temp2,temp3;//平面をmap[y]の短冊切りにする、シートのある地点を１Bit
void setMap(int n,int type){
int x1,y1,x2,y2,ansS=0,ansR=0;
for(int i=0;i<size;i++)map[i].reset();
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
y1++;
y2++;
x1++;
x2++;
temp.reset();
temp.flip();
temp>>=(size-x2+x1);
temp<<=(x1);
for(int y=y1;y<y2;y++){
map[y]|=temp;
}
}
int t;
for(int i=1;i<size;i++){
temp=map[i];
std::cout<<temp<<" "<<temp.count()<<"\n";//計算に使うマップの表示、シートがある部分が１無い部分が０最後尾にCount関数で求めた行の１の数が出るはずなのですが？
temp2=map[i-1];
t=temp.count();
ansS+=t;
ansR+=2*t;
//上段と下段で切れ端の共通辺を取り除く
temp3=temp&temp2;
ansR-=2*temp3.count();
//切れ端の両端を計算する
temp2=map[i];
temp3=(temp<<1);
temp3^=temp2;
ansR+=temp3.count();//切れ端の片端を計算する
temp3=(temp>>1);//もう片端を計算する
temp3^=temp2;
ansR+=temp3.count();
}
if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}

■No62619 (堀江伸一さん) に返信
> 質問2
中略
> なぜtemp.countとstd::cout<<tempで表示した１の数が一致しないのでしょうか？
知恵袋の方（笑）から来ました。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1073799400
に詳細な返答を書きましたが、
const int size=32;
にすれば面積は出ると思います。周長は異なるみたいですが。

uso8megaさんありがとうございます。
コード修正してジャッジデータ（採点用データ）無事通りました。
短冊に切ったシートの上下を２回余分に引いてたのが周長の間違いのもとでした。
下記コードは計算量が安定する代わりにコード実行速度が遅めという欠点があります。
コード実行速度が遅いと不正解となってしまうのですがこのコードの高速化はちょっと思いつきません。

このスレの最初のコードを高速化するか、模範解答の考え方の解説を頂けたらと思います。

#include<stdio.h>
#include <bitset>
#include <iostream>
const int size=10016;//縦横のマップサイズとりあえずサンプルデータを試せるサイズに限定
std::bitset<size> map[size],temp,temp2,temp3;//平面をmap[y]の短冊切りにする、シートのある地点を１Bit
void setMap(int n,int type){
int x1,y1,x2,y2,ansS=0,ansR=0;
for(int i=0;i<size;i++)map[i].reset();
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
y1++;
y2++;
x1++;
x2++;
temp.reset();
temp.flip();
temp>>=(size-x2+x1);
temp<<=(x1);
for(int y=y1;y<y2;y++){
map[y]|=temp;
}
}
int t;
for(int i=1;i<size;i++){
temp=map[i];
//std::cout<<temp<<" "<<temp.count();//<<"\n";計算に使うマップの表示、シートがある部分が１無い部分が０最後尾にCount関数で求めた行の１の数が出るはずなのですが？
temp2=map[i-1];
t=temp.count();
ansS+=t;
ansR+=2*t;
//上段と下段で切れ端の共通辺を取り除く
temp3=temp&temp2;
ansR-=2*temp3.count();
//切れ端の両端を計算する
temp2=map[i];
temp3=(temp<<1);
temp3^=temp2;
//std::cout<<"("<<temp3.count()<<")\n";
ansR+=temp3.count();//切れ端の片端を計算する
}
if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}

追記に気付かなくて済みません。rssとか変更通知とかが無い場所は、定期的に監視する対象が基本決まっていますもので。

＞下記コードは計算量が安定する代わりにコード実行速度が遅めという欠点があります。
擬似的なbitblt（メインメモリとVRAM間の転送）みたいな処理[temp→map]なので、遅いのは無理もありません。GPUにでも任せたくなる処理ですね。

＞模範解答の考え方の解説を頂けたらと思います。
出力結果が正しいなら、JOIの解説は殆ど実行できている筈ですので特に問題は無いかと。
あえて目立つ部分を補足するならば
＞集合とか苦手なので良く分からなず
シートが多重重ねになっている部分を正しく処理できていれば、∪（論理和）とか特に気にすることはないでしょう。まぁsheetIOでのシート重ね差分の記録＆tempIOによる一重化は少々冗長な気もしますが、データ的に分かり易くもありますし。
>>入力をあらかじめ並べなおしておけば，さらに効率良く
恐らく、入力ファイルの一グループｎ個分をまとめ読みしておいて、y1が小さくy2が大きい順にでも並べ替えておいてから処理した方が、シート重ね処理を簡便化し易いと思います。次処理シートの当てはめ位置の検索とか、次処理シートが処理済シートに完全に重なっているので追加不要になりがちとか。
>>線形リスト
std::listのことかな？恐らくシート重ね処理での煩雑な要素の追加・削除をできるだけ少なくしたいのだと思います。大メモリ領域の確保・解放・複写は比較的重くなりがちな処理ですし。OOPだと目立ちにくい所でコンストラクタ＆デストラクタが大量に実行されたりして、更に重くなりがちですから。

＞このスレの最初のコードを高速化する
済みませんあんまり興味が無かったんでコードは精査していないんですが、自分が作るとしたら恐らくシート重ね処理の中でシート重ね枚数差分情報のsheetIO&tempIOを介さずに直接std::vector<col> tate[10000/*Ｘ座標*/];を構築するように記述すると思います。ってかJOI解説もこれを線形リストで構築する前提で書いてあるように思えます。
tate[]の中で、次処理シートが処理済シートに重なっていなければ単純挿入するだけですし、重なっていれば（ピッタリ隣接分も含む）重なっている範囲の全処理済シート群＋次処理シートを１枚分にまとめて[y1=min(範囲内全y1), y2=max(範囲内全y2)]置き換えます。この置き換え処理が、線形リストだとかなり低コストに実行できそうです。
sheetIO+tempIOでの処理だと、複数毎重ねては潰し重ねては潰ししていてその都度Ｙ軸方向にトレースかけているので、この部分の処理がネックになっていそうですし。

すみませんが指摘できるのは現状ソレ位です。JOI2006の問題５の入力8/9は10000四角もあるのに持ち時間が60秒？で1四角当たり6msec以内で処理せよってのは少々ハードル高めかもしれません。

コード解けました。
集合は苦手ですが丁寧に考え直してコードから組みなおしたらうまくいきました。
コード実行速度１位正当しました。
少しうれしいです。

#include<stdio.h>
#include<vector>
#include <algorithm>
#include <string.h>

const int typeIn=1,typeOut=-1,mapSize=10003;

struct point{
int x1,x2,y,inOut;
bool operator<(const point p)const{
if(y!=p.y)return y<p.y;
return inOut>p.inOut;
}
};

void setMap(int n,int type){
std::vector<int> sheetIO[mapSize];//シートにinOut[x座標]する。Y座標は０から増えていく
std::vector<point> points;
point p1,p2;

int x1,y1,x2,y2,x,y,ioCount[mapSize];
memset(ioCount,0,mapSize*4);

p1.inOut=typeIn;
p2.inOut=typeOut;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++;//0列目はダミーとして使うので一列シートをずらす
x2++;
p1.x1=p2.x1=x1;
p1.x2=p2.x2=x2;
p1.y=y1;
p2.y=y2;
points.push_back(p1);
points.push_back(p2);
}
std::sort(points.begin(),points.end());
int ansR=0,ansS=0,old,now,pSize=points.size();//周長,面積、一列手前、今計算中の列、
for(int i=0;i<pSize;i++){
p1=points[i];
//printf("(%d %d %d %d)",p1.y,p1.inOut,p1.x1-1,p1.x2-1);
for(int x=p1.x1;x<p1.x2;x++){
if(sheetIO[x].empty() || ioCount[x]==0){
sheetIO[x].push_back(p1.y);
ioCount[x]=1;
}else{
ioCount[x]+=p1.inOut;
if(ioCount[x]==0){
sheetIO[x].push_back(p1.y);
}
}
}
}

int yOld1,yOld2,yNow1,yNow2,pSize2;
unsigned int pointer1,pointer2;

for(int x=1;x<mapSize;x++){
pSize2=sheetIO[x].size();
for(int i=0;i<pSize2;i+=2){
ansS+=sheetIO[x][i+1]-sheetIO[x][i];
ansR+=2*(sheetIO[x][i+1]-sheetIO[x][i])+2;
if(i!=pSize2-2 && sheetIO[x][i+2]==sheetIO[x][i+1]){
ansR--;
}
}

pointer1=pointer2=0;
while(pointer1<sheetIO[x-1].size() && pointer2<sheetIO[x].size()){
yOld1=sheetIO[x-1][pointer1];
yOld2=sheetIO[x-1][pointer1+1];
yNow1=sheetIO[x][pointer2];
yNow2=sheetIO[x][pointer2+1];

if(yOld1>=yNow2){
pointer2+=2;
}else if(yOld2<=yNow1){
pointer1+=2;
}else if(yOld2>=yNow2 && yOld1>=yNow1 && yOld1<=yNow2){
ansR-=2*(yNow2-yOld1);
pointer2+=2;
}else if(yOld2>=yNow2 && yOld1<=yNow1){
ansR-=2*(yNow2-yNow1);
pointer2+=2;
}else if(yOld2<=yNow2 && yOld1<=yNow1 && yOld2>=yNow1){
ansR-=2*(yOld2-yNow1);
pointer1+=2;
}else if(yOld2<=yNow2 && yOld1>=yNow1){
ansR-=2*(yOld2-yOld1);
pointer1+=2;
}
}
}

if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}

2011/10/24(Mon) 17:43:55 編集(投稿者)
2011/10/24(Mon) 17:43:45 編集(投稿者)

uso8mega さんお返事ありがとうございます。
usoさんの返答を読む前にコードが出来てたのですがかなりいい感じのコードになりました。

uso8megaさんの処理とは少し違うもののほぼ同じ処理のようです。

右端から一列ずつ処理すればもう少し速くならないか、コードを短くできないかなどいろいろ試行中です。

他の正答者のデータをみると、コードは相当短くできるようなので、どうすればコードが短くなるかいま考え中です。

シートにはいる出るのデータを作る処理と周長と面積の集計処理を統合できたらもう少しコードが短くなるかもしれません。

この問題高校生が１時間以内にノーヒントで解くことを期待されて出題されているというのに私ときたら答えの考え方までよんでも苦戦したなんて少しへこみます。

どなたでも結構ですがもう少しアドバイスをいただけたら幸いです。

GPU処理、勉強してみましたが中々奥深そうですね。

■No62654 (堀江伸一さん) に返信

質問の回答ではありませんが、
ソースコードを貼る場合は、「投稿モード」の図表モードにチェックすればインデントされます。

充分満足な高速処理に自力で辿り着かれたようで、何よりです。
メモリイメージから察するに入力をy1/y2順にバラして整列したので
Ｙ軸トレースを一回で済ませられている様で、十分な速度でしょう。
これを一時間以内に解ける人は適性が一般人から逸脱していますので、
そうお気になさらなくとも十分だと思いますが。私が現役開発者だった
頃には、もっと酷い人達が大勢開発現場にいましたし。この問題を
絶対解けないような人達も、フツーに開発現場にはいますよ。

この手の論理問題も面白いは面白いですが、業務ではもっとずっと
単調だが状態が多様で場合分けが多い大量処理の手早い解決の方が
求められがちだったりするので、程ほどで済ませて重要事項を優先
される事をお勧めしておきます。現場では分かり易さが優先される
事もあったりするので、過剰な最適化が不採用になったりしますし。

独学なもので業務に適した勉強というものが未だよくわからないのです。
＞Ｙ軸トレースを一回で済ます。
こういう風に概念で問題をとらえられるというのは憧れます。
私無学なもので当たり前のことを当たり前に分解して、当たり前に言えることだけを組み合わせてコード化する以上の分析手法を何も知らないのです。

Webサイトなどを見てますと、１ページ１００項目くらいあるデータを表示したり編集したりする画面とシステムを作る能力が要求されるようですが、イメージ湧きません。

やじゅさんありがとうございます。
次回からその機能を使うことにします。

うーんいろいろ考えましたがこのコードをこれ以上高速化する方法を当分考えつきそうもありません。
とりあえず解決とします。

C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[9]: プログラムの練習問題でわからないことが

過去ログには書き込み不可