Hacker Cup 2013 Round1

全問正解で、なんとかRound 2進出です。

Card Game

ソートして、組み合わせの数を数えました。数字が大きかったのでフェルマーの小定理使おうと思いましたが、自宅PC使えるのでメモリ2Gまでいけるなと気付いてパスカルの三角形を使いました。

Security

順列、辞書順最小の時点で「あ、フロー系だな。」と気付きました。貪欲に選んでいく方法をどうするか迷って、最小費用流か？と脇道にそれつつも、なんとかGreedyに文字を固定しながら二部グラフの完全マッチングすればいいと気付いて、解けました。

Dead Pixels

最初は、二次元BITかセグメントツリー系の問題かなと思いました。が、メモリ足りないなと気付いて、booleanだったらメモリに乗るな。となって、座標圧縮して画素がつぶれているかどうかをbooleanで持てばメモリ的にはいけそうだなと気付きました。それでも時間計算量的にはNGだったのですが、よほど作為的なケースじゃない限り現実的な時間で解けそうな気がしたので思い切ってテストケースDL。無事時間内にsubmitできました。
とりあえず解けたもののアルゴリズムの選択が正しかったのか正確には理解できていません。