YSF(J)H006 忘備録
YSF(J)H006
参加ありがとうございました。本来は部活のメンバーのみで行う予定でしたが、想定以上の人数が参加してくれて驚きでした。
今回はBとEのWriterをさせていただきました。
A
文字通り実装してください
cout<<"HelloWorld\nLoveNanashi"<<endl;
とかでいいんじゃないでしょうか。
B
配列でi番目のゲートが次いつ開くか、を保存する。というのが想定解でした。
各車両について、入る時間がゲートが開く時間以降であった場合、開くまでの時間を足していく…といった感じです。
また、配列をPriority_queueなどにすると実装が軽くなります。
計算量は前者の場合はO(TN)、後者の場合は挿入にlogNかかるのでO(TlogN)となります。
C
高々5本なので、全通りを試しても構いません。通り数は5C3より20通りです。
また、bit全探索を行うことにより、楽に実装をすることができます。
計算量は25なので十分に間に合います。
D
これ難しくないですか?きれいな解法がわかりません。
差の通りは高々4通りです。
1つ目から各差を足してって、正しいのが4つになったときに残りの一つがおかしい。それがなかったら最初がおかしいという風に説くことができます。
E
DP[i][j]をi回目の操作でMで割った余りがjであるものの通り数、という風に定義します。
1回目の動作にてDP[0][(1~6)%M]+=1とします。
i回目の動作以降、j(0~M)に対してDP[i][(j*(1~6))%M]+=DP[i-1][j]とします。
N回までの動作が終わったとき、DP[N-1][K]が答えとなります。
また、適宜modをとっていってください。計算量はO(NM)です。
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となります。
面積が求まったら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);
