(多分)今年最後のSRMであろう、SRM643参加しました。
簡易解説と一緒にコードを貼っていきます。
SRM的にはいつもの時間帯(日本時間での深夜)でしたが、ちょっと年末でドタついてる時の深夜はちょっと厳しかったです。正直、middleまではすぐとけたのですが、HARDが問題文を読んでもうまく理解できず、さらに解く気力もどんどん抜けていってしまったため、最終的にmiddle止まりでした。しかも、そのmiddleも制約を勘違いして落ちました。
250 : TheKingsArmyDiv2
問題概要
幸福な兵士とそうでない兵士の配列、stateが与えれる。
ある、state[i][j]==’H’の時その兵士は幸福であり、その兵士に隣接する兵士に幸福な兵士がいるとき、周りの兵士を次の時間に幸福にする。
また、とある兵士にコストをかけることでその兵士を幸福にすることができる。
全ての兵士を幸福にするために最低限必要なコストを返す。
解法
この問題では、隣接している兵士が幸福なとき最終的に伝播して全ての兵士が幸福になるため、仮に全ての兵士が幸福でない場合でも任意の2人の兵士にコストをかけて幸福にすれば、最終的に全ての兵士が幸福になるので、最終的な答えは{0,1,2}のいずれかになります。
兵士の中に1人でも幸福な人がいればその隣を幸福にすればいいので、答えは1、さらにその時四方に他の幸福な兵士がいればコストをかけずに全て幸福になるため、答えは0、1人もいなければ前述のように2人幸福にすればいいので、答えは2になります。
コード
500 : TheKingsFactorization
問題概要
Nを素因数分解した結果をVectorで出力せよ。
ただし、ヒントとして、答えの素数配列の一部primesが与えられる。
primes[i]は、答えの素数配列[2i]に等しい。
解法
Nの最大が10^18なので、そのままでは間に合いません。(最初ここ見間違えて、普通に素因数分解してため本番は落ちました)
しかし、ヒントとして素数の数が半数わかっているため、これを利用することでNのサイズが削減できます。
素因数の最大は、Nが10^18なので√N=10^9です。さらにその10^9程度の素因数は最大でも2つまでしかありません。さらに言えば3つ以上の素因数があるとき、そのうちの半数(切り上げ)はヒントとして与えられるので、
コード
本番中には通せず、その後他の方のコードなどを参考に上記の解法を知り、そのコードに合わせて実装しました。
1000 : TheKingsTree
問題が再読してもよくわからなかったので、分かった後で追加します。