Areas on the Cross-Section Diagramを解いた話
問題
これが問題です。
このような感じですね。最終的にいくつ水がたまるか、という問題になっています。
※この場合だと
input:\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\
output:35 5 4 2 1 19 9
です(合計、個数、それぞれの水の量)
実装
Stackを使います。 今回は3つのStackを使って実装を行いました。
Stack1:\
の箇所
Stack2:水の量
Stack3:Stack2の水の場所に対応する\
の箇所
必然的にStack2とStack3の大きさは等しくなります。
それではステップごとに実装の仕方を見ていきましょう。
まずは上下を考えない\.../の場合を考えます。
この場合の水の量は右-左です。
これは、間の_の箇所が右-左-1箇所あり、右、左の斜め分が追加されるので右-左-1+1となります。
なので、\を見つけたらその箇所をStack1に詰めて、/を見つけたらStack1から取り出すことで、対応するものを見つけられて横の面積を求めることができます。
面積が求まったらStack2に面積、Stack3に\の場所を入れていきましょう(上記の場合だと(1,1),(4,5)を詰める)
最難関なのがこれが下のものとつながるかどうか、の判定になります。ここでStack3を使用します。
ここで当たり前のことを確認しますが、文字列を左から右に見ているため、必ず新しく出てくる/は右側にあることがわかります。
また、/がKeyとして面積を求めるので、\/となる水の最深部から順に上に面積を求めていっています。よって、判定する水がつながるとしたら必ずStackの一つ前のものとつながることがわかります。
判定ですが、1つ前との関係は上の図で言う上の2種類の関係しかありえません。
Stackを使用し、/に対応する\を探しているので、下のような関係は存在しないことがわかります。
つながる関係は、左上の関係のみとなります。
1つ下は、Stackの一つ前なので、Stack3の最後に入れたやつを取り出して、そいつが今対応している\よりも小さかったら水はつながることがわかります。
当たり前のこと~から/の判定は必要ありません。
水がつながることがわかったらつなげましょう。
Stack2から1つ取り出し、いま求めている面積とつなげ、Stack3から一つ取り出し、今の/と対応している\を代わりに入れてあげればOKです。
また、問題図の19のように、水位が上がると2つの水とつながる場合があります。Stack3から取り出すものが今対応している\より小さい限り繰り返すWhile文などを組むとよいでしょう。
Stackに詰めている関係により、最初に調べた水はどんどん下に行きます。よって出力はStack2の逆順に出力しましょう。
以下、Javaコードになります
String s=scan.next(); Deque<Integer>index=new ArrayDeque<Integer>(); Deque<Integer>size=new ArrayDeque<Integer>(); Deque<Integer>sizeindex=new ArrayDeque<Integer>(); for(int i=0;i<s.length();i++) { char ch=s.charAt(i); if(ch=='\\'){ index.addFirst(i); continue; } else if(ch=='/'){ if(index.size()==0) {} else { int p=index.pollFirst();// /に対する\ int S=i-p;// \/の面積 if(size.size()==0) { size.addFirst(S); sizeindex.addFirst(p); } else { while(true) {//\\//みたいな状態 if(size.size()==0)break; int x=sizeindex.pollFirst(); if(x>p) { S+=size.pollFirst(); } else { sizeindex.addFirst(x); break; } } size.addFirst(S); sizeindex.addFirst(p); } } } } if(size.size()==0) { System.out.println(0); System.out.println(0); return; } int ans[]=new int[size.size()]; long sum=0; int cnt=0; while(size.size()>0) { int x=size.poll(); sum+=x; ans[cnt]=x; cnt++; } System.out.println(sum); System.out.print(ans.length+" "); ans=revint(ans); printArray(ans);