(多分)今年最後のSRMであろう、SRM643参加しました。
簡易解説と一緒にコードを貼っていきます。
SRM的にはいつもの時間帯(日本時間での深夜)でしたが、ちょっと年末でドタついてる時の深夜はちょっと厳しかったです。正直、middleまではすぐとけたのですが、HARDが問題文を読んでもうまく理解できず、さらに解く気力もどんどん抜けていってしまったため、最終的にmiddle止まりでした。しかも、そのmiddleも制約を勘違いして落ちました。
250 : TheKingsArmyDiv2
問題概要
幸福な兵士とそうでない兵士の配列、stateが与えれる。
ある、state[i][j]==’H’の時その兵士は幸福であり、その兵士に隣接する兵士に幸福な兵士がいるとき、周りの兵士を次の時間に幸福にする。
また、とある兵士にコストをかけることでその兵士を幸福にすることができる。
全ての兵士を幸福にするために最低限必要なコストを返す。
解法
この問題では、隣接している兵士が幸福なとき最終的に伝播して全ての兵士が幸福になるため、仮に全ての兵士が幸福でない場合でも任意の２人の兵士にコストをかけて幸福にすれば、最終的に全ての兵士が幸福になるので、最終的な答えは{0,1,2}のいずれかになります。
兵士の中に１人でも幸福な人がいればその隣を幸福にすればいいので、答えは1、さらにその時四方に他の幸福な兵士がいればコストをかけずに全て幸福になるため、答えは0、１人もいなければ前述のように2人幸福にすればいいので、答えは2になります。
コード
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 TheKingsArmyDiv2 { | |
| public: | |
| int getNumber(vector<string> state) { | |
| int ans=2; | |
| int dx[]={1,-1,0,0}; | |
| int dy[]={0,0,1,-1}; | |
| for (int i=0; i < state.size(); i++) { | |
| for (int j=0; j < state[i].size(); j++) { | |
| if(state[i][j]=='H') | |
| { | |
| ans=min(ans,1); | |
| for(int x=0;x<4;x++) | |
| { | |
| if(i+dx[x]>=0&&i+dx[x]<state.size()&& | |
| j+dy[x]>=0&&j+dy[x]<state[i].size()&& | |
| state[i+dx[x]][j+dy[x]]=='H' | |
| ) | |
| ans=0; | |
| } | |
| } | |
| } | |
| } | |
| return ans; | |
| } | |
| }; |
500 : TheKingsFactorization
問題概要
Nを素因数分解した結果をVectorで出力せよ。
ただし、ヒントとして、答えの素数配列の一部primesが与えられる。
primes[i]は、答えの素数配列[2i]に等しい。
解法
Nの最大が10^18なので、そのままでは間に合いません。(最初ここ見間違えて、普通に素因数分解してため本番は落ちました)
しかし、ヒントとして素数の数が半数わかっているため、これを利用することでNのサイズが削減できます。
素因数の最大は、Nが10^18なので√N=10^9です。さらにその10^9程度の素因数は最大でも2つまでしかありません。さらに言えば3つ以上の素因数があるとき、そのうちの半数(切り上げ)はヒントとして与えられるので、![\sqrt[3]{10^{18}} = 10^6](https://s0.wp.com/latex.php?latex=%5Csqrt%5B3%5D%7B10%5E%7B18%7D%7D+%3D+10%5E6++&bg=ffffff&fg=000&s=0&c=20201002)
以上の不明な素因数はたかだか1つしか存在しないことになります。そのため、それ以下の素因数を全て試し割りなどで列挙した後、残った値を含めることで最終的な答えになります。
コード
本番中には通せず、その後他の方のコードなどを参考に上記の解法を知り、そのコードに合わせて実装しました。
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 TheKingsFactorization { | |
| public: | |
| vector<long long> getVector(long long N, vector<long long> primes) { | |
| for (int i=0; i<primes.size() ;i++) { | |
| N/=primes[i]; | |
| } | |
| for (int n=2; n<1000000&&N>1; n++) { | |
| if(N%n==0) | |
| { | |
| primes.push_back(n); | |
| N/=n; | |
| n–; | |
| } | |
| } | |
| if(N>1) | |
| primes.push_back(N); | |
| sort(primes.begin(),primes.end()); | |
| return primes; | |
| } | |
| }; |
1000 : TheKingsTree
問題が再読してもよくわからなかったので、分かった後で追加します。