naoya_t@hatenablog

いわゆるチラシノウラであります

HourRank 22

HackerRankさんのところのやつ

タイムシフト参戦、というか後から(本番は1時間で3問らしいのでタイムリミット1時間で)問題を覗いてみた。

Parity Game - AC 15 / 15

[Success Rate: 71.14% Max Score: 15 Difficulty: Easy]

合計が奇数 = 奇数が奇数個 奇数が偶数個なら0 奇数が奇数個なら…1つ以上は取らないといけないから、n>1なら1つ取れて、n=1なら-1 というか collections.Counterで殴るやつ https://www.hackerrank.com/contests/hourrank-22/challenges/mancunian-and-parity-game/submissions/code/1302232093

Super Mancunian - WA 24.38 / 50

[Success Rate: 13.75% Max Score: 50 Difficulty: Medium] これって最小全域木問題では? 最後に繋ぐ(というか繋ぐ中で一番コストの高い)やつを無料化すればいい その最小コストを叩き出す選択肢がいくつあるかはどう求める? 最後に繋ぐやつの前の2つの島を結ぶ辺がいくつあるか? という視点で書いたWA(部分点あり)解: https://www.hackerrank.com/contests/hourrank-22/challenges/super-mancunian/submissions/code/1302232353 最後に繋ぐやつが、そこまでに繋いだ中で一番コストの高い「唯一の」辺とは限らない、よね 高コスト一位タイのやつを繋ぐ順番を総当りするとか?全部の辺が同コストだったら時間的に無理では? とか考えた辺りまで

Candy Collection

[Success Rate: 2.70% Max Score: 70 Difficulty: Hard] 問題は読んだ ・同じ色の箱は一緒にできない ・違う色どうしで組み合わせ(というかbitwiseOR値)を最適化しないといけない ・ある2箱のbitwise ANDが0なら、そいつらは同乗してもしなくても同じ ・0でないなら同乗させたほうがお得 ・違う色の同じ数のやつはとりあえずグループしていいのか? ・LSB寄りかMSB寄りかはあまり関係なくて、支払うビット数を少なくできればいいのか? ・共通するビット数が多いやつから貪欲に繋いでいっていいのか? とか考えた辺りまで

結果

部分点を合わせて39.38点。所要時間も含めると110位台か。 本番では参加者2303人、全完(135点)が8人。