SRM641参加しました。
またしても、簡易解説もどきと一緒にコードを貼っていきます。
今回は翌朝用事があったので、CODEINE Phaseが終わったら、そのまま離脱したのですが、終了5秒前にHardをSubmit、その5分後にバグがあることに気づくという慌ただしい回でした。なお、Hardは翌日確認したらやはりシステムテストで落ちてました。
easyとmiddleは、結構早く通せていい感じだったのですが、Hardでつまり、さらにHardのバグに気づいたあと直せると思った手法も誤りがあり、結局再修正が必要と散々な結果でした。
250 : BuyingTshirts
問題概要
Quimey と Pabloがそれぞれ、時間iにQ[i]、p[i]の資金を得て、T以上の資金を持った時、Tシャツを購入する。
Quimey と PabloがTシャツを同じ時間に買うタイミングは何回起こるかを答える。
解法
iは最大100なので、時間0～i-1まで2人の手持ち金額を確認し、同時にTを超えるタイミングを数えればOKです。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class BuyingTshirts { | |
| public: | |
| int meet(int T, vector<int> Q, vector<int> P) { | |
| int ans=0; | |
| int qq=0; | |
| int pp=0; | |
| for(int i=0;i<Q.size();i++) | |
| { | |
| qq+=Q[i]; | |
| pp+=P[i]; | |
| if(pp>=T && qq>=T) | |
| ans++; | |
| if(pp>=T) | |
| pp-=T; | |
| if(qq>=T) | |
| qq-=T; | |
| } | |
| return ans; | |
| } | |
| }; |
500 : TrianglesContainOriginEasy
問題概要
複数の点のX,y座標が与える。
その点で三角形を作る時、座標(0,0)を内部に含む組み合わせが何通りあるかをカウントする。
解法
点の数は最大50のため、3重ループで点の組み合わせの全探索を行っても時間的に問題ありません。
三角形と点の内包関係の判定は、それぞれの辺と点の位置関係を見て、同一方向にあるか否かで判定できます。
(ただ、例のごとく私の幾何ライブラリはほとんどないため、判定部分はこちらのサイトのコードを利用しました。)
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| struct point | |
| { | |
| point() : x(0), y(0) { } | |
| point(double x_, double y_) : x(x_), y(y_) { } | |
| double x, y; | |
| }; | |
| point operator-(const point& a, const point& b) { return point(a.x – b.x, a.y – b.y); } | |
| point operator+(const point& a, const point& b) { return point(a.x + b.x, a.y + b.y); } | |
| typedef point vector2d; | |
| // 外積を求める | |
| double cross(const vector2d& a, const vector2d& b) | |
| { | |
| return a.x * b.y – a.y * b.x; | |
| } | |
| // 点 p が反時計回りの三角形 abc の内側にあるかどうか判定 | |
| bool point_in_triangle(const point& p, const point& a, const point& b, const point& c) | |
| { | |
| // p が ab の右側にあれば三角形の外側にある | |
| if (cross(p – a, b – a) < 0.0) return false; | |
| // p が bc の右側にあれば三角形の外側にある | |
| if (cross(p – b, c – b) < 0.0) return false; | |
| // p が ca の右側にあれば三角形の外側にある | |
| if (cross(p – c, a – c) < 0.0) return false; | |
| return true; | |
| } | |
| class TrianglesContainOriginEasy { | |
| public: | |
| int count(vector<int> x, vector<int> y) { | |
| int ans=0; | |
| for(int i=0;i<x.size();i++) | |
| for(int j=i+1;j<x.size();j++) | |
| for(int k=j+1;k<x.size();k++) | |
| { | |
| if(point_in_triangle(point(0,0),point(x[i],y[i]), point(x[j],y[j]) | |
| , point(x[k],y[k]))|| | |
| point_in_triangle(point(0,0),point(x[i],y[i]), point(x[k],y[k]) | |
| , point(x[j],y[j]))|| | |
| point_in_triangle(point(0,0),point(x[j],y[j]), point(x[i],y[i]) | |
| , point(x[j],y[j]))|| | |
| point_in_triangle(point(0,0),point(x[j],y[j]), point(x[k],y[k]) | |
| , point(x[i],y[i]))|| | |
| point_in_triangle(point(0,0),point(x[k],y[k]), point(x[i],y[i]) | |
| , point(x[j],y[j]))|| | |
| point_in_triangle(point(0,0),point(x[k],y[k]), point(x[j],y[j]) | |
| , point(x[i],y[i]))) | |
| ans++; | |
| } | |
| return ans; | |
| } | |
| }; |
900 : ShufflingCardsDiv2
問題概要
2n個の要素を{1,2,3…,2n}の順で持つ数列を以下の手順で2回シャッフルする。
- 現在の数列の先頭n文字を数列A,後方n文字を数列Bと分ける。
- 数列Aと数列Bを任意の順番にシャッフルする
- {A[0],B[0],A[1],B[1]…A[n-1],B[n-1]}という順序でマージした数列をあたらしい数列とする
この2回のシャッフルで数列permutationが作成できる場合、”Possible”を、作成できない場合、”Impossible”を返す。
解法
本番中は、{1…2n}からpermutation作ると誤読して、そもそも間違ってました。
手順2の数列の組み合わせは無数にあるので、単純に探索すると厳しいですが、シャッフル回数が2回のため、到達すべき数列から判定することもできます。はじめに1度目のシャッフル後、数列Aは最終的な数列(permutation)の偶数番目の要素番号の要素を持ち、数列Bは奇数番目の要素番号の要素を持っておく必要があります。さらにこの時の数列Aは、1回目のシャッフル後の数列の先頭N文字です。この先頭N文字は、1回めのシャッフル中の際、{A0[0],B0[0],…,A0[(n-1)/2],B0[(n-1)/2]}のようにして作られます。そのため、最初のシャッフル時に数列A0,B0に分けた後、A0,B0それぞれからこの個数の要素を抜き出して数列Aを作るため事ができれば、permutationは作成可能ということになります。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class ShufflingCardsDiv2 { | |
| public: | |
| string shuffle(vector<int> permutation) { | |
| const int n=permutation.size(); | |
| vector<int> ga,gb; | |
| for(int i=0;i<n;i++) | |
| { | |
| if(i%2==0) | |
| ga.push_back(permutation[i]); | |
| else | |
| gb.push_back(permutation[i]); | |
| } | |
| sort(ga.begin(),ga.end()); | |
| sort(gb.begin(),gb.end()); | |
| vector<int> a,b; | |
| int ac=0; | |
| int bc=0; | |
| for(int i=1;i<=n;i++) | |
| { | |
| if(i<=n/2) | |
| a.push_back(i); | |
| else | |
| b.push_back(i); | |
| } | |
| for(int i=0;i<ga.size();i++) | |
| { | |
| if(find(a.begin(),a.end() ,ga[i])!=a.end()) | |
| ac++; | |
| if(find(b.begin(),b.end() ,ga[i])!=b.end()) | |
| bc++; | |
| } | |
| if(ac==(n/4)+(n/2)%2) | |
| return "Possible"; | |
| else | |
| return "Impossible"; | |
| } | |
| }; |
厳密には今回の解法では、permutationを数列A,Bに分ける際、Aが決まれば自動的にBも決まるため、Aのみの判定で大丈夫なのですが、最初に書き始めた際に一旦保存していたのと、合ったほうがわかりやすいかと思ったので、残しています。