数年前に、競プロを本格的に始めたばかりの頃にTopcoderをよくわからないまま使う→システムテストで落ちまくって、レーディングが下がるだけの簡単なプロセスを繰り返してました。それがちょっとしたトラウマで、今までずっと未参加だったTopcoderを改めて参加しようと、今回のSRMに参加しました。せっかく参加したので、簡易解説もどきと一緒にコードを貼っていきます。
250 : ElectronicPetEasy
問題概要
2匹のペットが居る。それぞれ、st1からt1の間隔でp1回、st2からt2の間隔でp2回餌を与える。同じタイミングで餌を与える場合があれば、 “Difficult”、そうでなければ、”Easy”を返す。
解法
全ての変数において 最大1,000 なので、全探索で間に合うはずです。
ただ私は、1匹目のタイミングを全てsetに入れて、2匹目に同じタイミングがあれば、”Difficult”、そうでなければ、”Easy”を返しました。
コード
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 ElectronicPetEasy { | |
| public: | |
| string isDifficult(int st1, int p1, int t1, int st2, int p2, int t2) { | |
| set<int> hash; | |
| for(int i=0;i<t1;i++) | |
| { | |
| hash.insert(st1+(i*p1)); | |
| } | |
| for(int i=0;i<t2;i++) | |
| { | |
| if(hash.count(st2+(i*p2))!=0) | |
| return "Difficult"; | |
| } | |
| return "Easy"; | |
| } | |
| }; |
500 : AliceGameEasy
問題概要
Alice と Kirito がゲームをして、それぞれ合計点がxとyになった。
ゲームの得点は、それぞれ1回毎に 1,2,3,4,5… と増えていく。
x,yが与えられるので、そのx,yを満たす最小のAliceの勝利回数を返す。
そのようなx,yがありえない場合には-1を返す。
解法
x+yは全てのゲームの合計点なので、必ず1+2+…nの累積和になります。
そのため、x+yがあるnの累積和として成り立たない場合、-1になります。
また、累積和は以下の公式で求められます。
このnを二分探索で求めます。もし式を満たすnがなければ、累積和ではないため、その時点で-1を返します。
nが求まれば、nから順番に大きい値をxから引いていき、x=0となる時の値の個数を返すことで、答えとなります。
コード
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 AliceGameEasy { | |
| public: | |
| long long findMinimumValue(long long x, long long y) { | |
| long long ans = 0; | |
| long long sum = x+y,r=0,l=3037000490; | |
| long long i=(r+l); | |
| while(true) | |
| { | |
| i=(r+l)/2; | |
| if((i*(i+1))/2 == sum) | |
| break; | |
| else if((i*(i+1))/2 > sum) | |
| l=((r+l)/2)-1; | |
| else if((i*(i+1))/2 < sum) | |
| r=((r+l)/2)+1; | |
| if(r>l) | |
| return -1; | |
| } | |
| while(x>0) | |
| { | |
| if(x>=i) | |
| { | |
| ans++; | |
| x-=i; | |
| i–; | |
| } | |
| else | |
| { | |
| i=x; | |
| } | |
| } | |
| return ans; | |
| } | |
| }; |
1000 : BoardFoldingDiv2
問題概要
0と1のみが要素として含まれるM列N行の2次元配列のパズルが与えられる。
パズルは、折りたたんだ際に重なる0と1の対応が同じ場合、折りたたむ事ができる。(パズルをはみ出す形では折れない)
パズルがまだ折れる場合でも、任意の時点で止める事ができる。
このルールにしたがって、作られるパズルのパターン数を返す。
解法
折りたためるパターン数の列挙なので、パターンをsetにいれて、新しいパターンを作れなくなるまで全ての折り目の候補で折れるかを判定する方針で実装してましたが実装が間に合ってないので、合っているかは不明です。
上記の方針だと大きいケースの場合、TLEしました。解法を理解した後、書き直します。
コード
本番中に間に合いませんでした。別途、Practiceで書いてシステムテスト通ったらコード載せます。