SRM650参加しました。
今回は、日本時間では平日11時開始と、個人的には本来参加しやすい時間帯だったのですが…
ちょっと東京に行く用事があり、ちょうど帰るつもりの時間帯と重なりそうだったので、待合室でeasy,Medium書いて、新幹線内でhard解こうと思ってたら、まさかホテルに忘れ物をしてしまいました。
取りに戻ったりしてたら、駅に戻ってこれたのが、新幹線の時間ギリギリになってしまい、乗って落ち着いたのが11時40分頃…
そこから解き始めたので、Coding Phaseがセルフ短縮(しかも点は下がる)状態に…
するめセルフハードモード(Div2)
— ik-fib (@ik11235) February 18, 2015
それでもレートが下がらなかった(むしろ、やっと1000台到達できた)のでよかったですが、逆にMediumまではすぐ解けるけど、Hardでいつも解けないまま終わってる状態なのが、余計にはっきりしたことになりました。今後は、Hardを本番中に通せるように…
(rating: 968 -> 1015)
- 250 : AC
- 500 : AC
- 1000 : no submit
- Challenge AC : no Challenge
250 : TaroJiroDividing
問題概要
整数A,Bが与えられる。それぞれの値が奇数になるまで2で割り続ける過程での値で、それぞれに共通する値の数を答える。
解法
値の上限は、1,000,000,000(=10^10,10億)ですが、計算で含まれる値の数は、この数値を2で割り続けて発生する値なので、最大でもlog2(10^10)≒30個程度です。そのため、A,Bごとに含まれる値を全て計算した後、両方に共通する値の数を探索すればOKです。
ただし、AまたはBが最初から奇数の時にその値自身を加える処理を忘れずにする必要があります。
コード
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 TaroJiroDividing { | |
| public: | |
| int getNumber(int A, int B) { | |
| set<int> hash; | |
| hash.insert(A); | |
| for(;A%2==0;) | |
| { | |
| A/=2; | |
| hash.insert(A); | |
| } | |
| int cnt=0; | |
| if(hash.count(B)!=0) | |
| cnt++; | |
| for(;B%2==0;) | |
| { | |
| B/=2; | |
| if(hash.count(B)!=0) | |
| cnt++; | |
| } | |
| return cnt; | |
| } | |
| }; |
値の探索は単純な探索でも間にあいますが、今回はAから作られる値をsetに格納、Bを割り続けて奇数になるまで、そのsetに現在の値が含まれているかをチェックしてカウントしています。
500 : TaroFillingAStringDiv2
問題概要
‘A’,’B’,’?’から構成される文字列Sが与えられる。この文字列で同じ文字が隣接する箇所の個数を答える。ただし、’?’は’A’,’B’いずれかを任意で選んで入れる。隣接数が最小になるように’?’を埋めた時の隣接数を答えよ。
解法
この?の箇所の入れ方がほとんど決まっています。仮に?が一文字で独立している時を考えると、パターンとしては以下の2パターンのみになります。(AとBが逆の場合も同様)
- A?A
- A?B
上のパターンの場合、入る文字はBと決まっており、下のパターンの場合どちらの文字を入れても隣接数が増えるのでどちらを入れても同じため、どちらの場合でも先頭の文字ではない方をいれれば、最小になります。?の連続する数が2文字以上に増えても”ABAB…”,”BABA…”というパターンで進めていくのが必ず最小になります。この時、先頭、あるいは終端のどちらかで隣接数が増える場合(A??A,A???B等)、AB…”,”BA…”どちらのパターンでもかならず隣接数が1増えます。
そのため、?に入れる文字は必ず1つ手前の文字ではないものを入れれば最小になります。また、文字列の先頭が?で始まる部分は必ず隣接しないパターンが存在する(?の終端をその次の文字の逆にすればよい)ため、その部分は無視できます。後は、?を埋めた文字列内で同じ文字が隣接する箇所の個数をカウントすれば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 TaroFillingAStringDiv2 { | |
| public: | |
| int getNumber(string S) { | |
| if(S.size()<2) | |
| return 0; | |
| int ans=0; | |
| int i=0; | |
| while(S[i]=='?') | |
| i++; | |
| for (; i < s.size(); i++) { | |
| if(S[i]=='?') | |
| { | |
| if(S[i-1]=='A') | |
| S[i]=='B'; | |
| else | |
| S[i]=='A'; | |
| } | |
| if(s[i-1]==s[i]) | |
| ans++; | |
| } | |
| return ans; | |
| } | |
| }; |
本番中は、’?’の箇所全ての先頭が、Aの場合、Bの場合を作成し、最小の方を選ぶという方式でやっていましたが、終了後整理すると上記のようにシンプルにできることがわかったので、書き直しました。
1000 : ABC
時間内に、問題把握まで進めませんでした…