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です。
コード
500 : TrianglesContainOriginEasy
問題概要
複数の点のX,y座標が与える。
その点で三角形を作る時、座標(0,0)を内部に含む組み合わせが何通りあるかをカウントする。
解法
点の数は最大50のため、3重ループで点の組み合わせの全探索を行っても時間的に問題ありません。
三角形と点の内包関係の判定は、それぞれの辺と点の位置関係を見て、同一方向にあるか否かで判定できます。
(ただ、例のごとく私の幾何ライブラリはほとんどないため、判定部分はこちらのサイトのコードを利用しました。)
コード
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は作成可能ということになります。
コード
厳密には今回の解法では、permutationを数列A,Bに分ける際、Aが決まれば自動的にBも決まるため、Aのみの判定で大丈夫なのですが、最初に書き始めた際に一旦保存していたのと、合ったほうがわかりやすいかと思ったので、残しています。