mayoko’s diary

プロコンとかいろいろ。

HackerRank

lay_contest beta round 00004 神による整地 (3)

問題 www.hackerrank.com 解法 まず基本的な解法ですが, 全部同じ値になったらそれが最適 そうでない場合は, 最大のものと最小のものを選択し, それぞれ -1, +1 する というのが最適です。この貪欲法を素直にやると 10%, map でやって少し工夫すると 30% の…

lay_contest round 00002 近所迷惑高橋くん

問題 www.hackerrank.com 解法 kmjp さんの解法を参考にしました。 kmjp.hatenablog.jpL bit の bitset を考えて, i bit 目が立っていたら, 「時刻 i に目覚ましが鳴る」と考えることにします。愚直にやるなら, 各 (A[i], B[i]) について, A[i] からスタート…

Saiko~ No Contesuto #03 歯車と箱

問題 www.hackerrank.com 解法 明らかに上半分を掛け算する方に使って下半分を割り算に使ったほうが得になります。ということで, この場合の分数の値を出力すればよいですが, C++ ではこれが面倒です。これをやるためには, 下半分の掛け算と上半分の掛け算の…

Saiko~ No Contesuto #01 わくわく排他的論理和

電車の中で考えて解法がわかったのでワクワクしながらコードを書いたんですが double 周りでつらみが生えた。 問題 www.hackerrank.com 解法 2 進数の各桁 i ごとに, そのビットが立つ確率 p_i を求めると, 期待値の線形性により, 答えは 2^0 * p_0 + 2^1 * …

Saiko~ No Contesuto #02 Waiwai Otaku Panic

問題 Programming Problems and Competitions :: HackerRank 解法 まず, 最短経路に含まれる辺以外は取り除きます。また, 頂点 0 からの距離が別のものは, 絶対に通る辺が被ることはありません(被るとすると, 距離が近い方の頂点はどこか寄り道してることに…

UnKoder #04

UnKoder #04 に参加しました。結果は内緒です。 topcoder以外のコンテストはたいていサンプルが甘いのでちゃんと注意深く問題を把握しないとダメですね。これからは意識的に気をつけていきたいです(C問題を単純な期待値の線形性を使ってやろうとしてハマった…

UnKoder #03 Rabbit Family

問題:Programming Problems and Competitions :: HackerRank解法:dp[n][mode] = (mode=1のとき,残り日数がn日のときに首輪をつけた小さいウサギが1匹いるときの首輪の付け方, mode=0のとき,残り日数がn日のときに首輪をつけていない小さいウサギが1匹いると…

UnKoder #03 Frog Jumping

UnKoder #03に参加。2完です。うーん。最近あんまり調子よくないですね。問題:Programming Problems and Competitions :: HackerRank解法:左側からのaの累乗の和と右側からのaの累乗の和が都会度の値となる。このように左側からの和と右側からの累乗の和を分…

UnKoder #02 Binary Matrix

気づかなかった…問題:Programming Problems and Competitions :: HackerRank解法:例えばひとつの列で0のビンゴがあったとすると,もう1が行でビンゴを作ることはありえなくなる(下図(0列に0のビンゴができている)のようになるので)。 0111 0111 0111なので,ビ…

UnKoder #02 Animal Party

最初もっと高速なアルゴリズムにするつもりだったけど,なんかWAが出るので方針を変えた。問題:Programming Problems and Competitions :: HackerRank解法:メモ化再帰を使う。問題の性質上,パーティーに招待される動物は イヌ->ネコ->イヌ->ネコ->... ネコ->…

UnKoder #02 Pass on Tree

UnKoder #02に参加。コメントが日本語に入っていると提出不可能になることに気づかず提出ができませんでした。ただそのあと提出できるようになってからも結構試行錯誤があったのでもしかすると提出できても1完くらいしかできなかったかも。問題:Programming …