【競プロ精進日記】HackerRank Thanks Kosen 2020

2020.03.27
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F
8. G

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

Thanks Kosen 2020
今年度高専を卒業する強強の競プロer４人で有志コンが開催されました。
私も今年度高専を卒業する競プロer（弱弱）の一人として参加しました。
それにしても同級生（writer）に黄コーダーがいたなんて知りませんでした。
一つ下と上にはレッドがいるんですが…

A

A – 青春占い
さすが高専っぽい問題ですね。
ちなみに私の学科は１年生のころ男：女が43：1でした。
N-MがK以上か判定しましょう。
https://www.hackerrank.com/contests/thankskosen2020/challenges/challenge-2438/submissions/code/1322174357

B

B – 15ヶ年計画
今の学年と現在の学年での留年回数、休学回数を持ちながら更新していけばよいです。
https://www.hackerrank.com/contests/thankskosen2020/challenges/15-5/submissions/code/1322174547

C

C – 採掘体験
題材に埼玉高専が使われてるのはwriterさんにいらっしゃるのかな？
アップグレードできる残金があるならば、ピッケルをアップグレードするしないで最終的な残金を比較してよい方を選択しましょう。
現在のターン数を$i(1,2,3…)$、残金を$m$、ピッケルのランクを$r$とすると、
$$ m – a + (n – i) * (r + 1) >= m + (n – i + 1) * r $$
ならばアップグレードしたほうが良いです。
https://www.hackerrank.com/contests/thankskosen2020/challenges/challenge-2429/submissions/code/1322174817

D

D – XOR?
いやぁー私には難しいですね。塾考しました。
解けるまでに考えたことはMで割り切れる数を半分全列挙して、残りの半分に選択できる個数を考えるというものでしたが、なんとも無理そうです。
そこで、xorの特性に注目するとA xor B = 1のときは(0,1),(1,0)の2通り、A xor B = 0のときは(0,0),(1,1)の2通りでA xor Bの値によらず、A,Bの選び方は2通りだということに気づきます。
つまり、数の桁数のみに依存し、A,Bの組み合わせの数が決まります。
数の桁数について、$min(C_A,C_B)$までの桁（2つの数が重なる）は各桁において2通り、はみ出た分の桁は各桁について1通りだとわかります（AとBが重ならないので）。
ここまでわかれば、A xor Bで作り出せる数の個数、すなわちMで割り切れる数の個数を計算し、上述の計算を行うとACです。
まとめると、下記になります。
$$ \left\lfloor \frac{2^{max(C_A,C_B)} – 1}{M} \right\rfloor \times 2^{min(C_A,C_B)} \times 1 $$
https://www.hackerrank.com/contests/thankskosen2020/challenges/xor-10/submissions/code/1322178288

E

E – インターン
解けてません。
素直に$A_i$とイン・アウトの2*10^5を持ってメモ化再帰するのかなと思ってコンテスト終了しました。
解説ACしました。
1方向に突き進んでいくものだと誤読していましたが、どこにもそんなことは書いてないですね。
ワープ後左右に動くことができると理解するものの自力ACできませんでした。
左右に歩けるとなると頂点間にエッジを張るというのは自然なアイデアですが、どの辺を歩くというのが問題です。
そこで、各番号で1度ずつワープし元に戻る（巡回できる）、というのがどういうことかと考えると、すべての頂点でワープ1回と左右への移動が1回限り行えるということです。
これが思いつけば、頂点の端（0番目）はワープ1回、右側（1番目）への移動の1回というように定まります。
2番目は1番目との移動の1回がすでに定まっているのでワープしなければなりません。
これをすべての頂点で考えていくと、そのような辺の張り方は一つに定まります。
辺の張り方さえ分かれば、どこの位置からでもいいですが、元の位置へと巡回できることが確認出来たらYesでACです。
なお、実際に辺を張ってグラフを作る必要はなく、iターン目が偶奇のときに現在の位置が偶奇の時、ワープor（左or右）に移動して現在位置を更新、というように記述するのが簡単でした。
https://www.hackerrank.com/contests/thankskosen2020/challenges/challenge-2428/submissions/code/1322197144

F

F – 卒業RTA
DPするというのはすぐ思いつきますが、私には実装難でした。
単位数の制約が小さいので、単位数と科目による日数の値でDPしましょう。
M種類の前述のDPとそれらの結果によるDPの計M+1回のDPをすれば解けます。
結果によるDPは、各種類のDPで最低必要単位数を満たす複数の値が出た場合すべての値を使用するということと、各種類のDPとは異なり結果によるDPは各種類すべての値を1度ずつ使用しなければならないことに注意しましょう。
私が苦戦したポイントは必要単位数以上取得した日数はまとめていいということ、
合計最低必要単位数より、各種類の最低必要単位数が上回る場合があることに気づくのが難しかったです。
最初はまとめずに巨大な配列を作っていたのでTLEしました…
https://www.hackerrank.com/contests/thankskosen2020/challenges/challenge-2448/submissions/code/1322198419