158.1

SRM

levelを書くのが面倒になってきた今日この頃。

250 (level1)

数式が与えられるので、N進数として計算した時に正しくなるすべてのNを答えよという問題。ただしNは2から20まで。


2から20までちゃんとデコードできますか、というだけの問題。桁数が5桁なのでintから溢れたりもしない。


デコードできないデータがあった時に例外を使わないといけないなぁと思いつつ、例外クラスを実装する気になれなかったので取り敢えずErrorを投げるという実装をしてしまうのは良くないよなぁ...。

500 (level2)

絵の具セットと、欲しい絵の具集合が与えられるので、欲しい絵の具を手に入れるのに必要な最小絵の具セット数を答えよという問題。


絵の具セットの種類が20で、欲しい絵の具集合のサイズが25までなので、2の20乗通りの組み合わせを試した上で、最小の絵の具セットで欲しい絵の具集合を実現できるものを求めればおしまい。

1000 (level3)

上下左右に1マス動くことができるゲームで盤面の一番上までいくのにかかる最短の時間を求めよという問題。ただし各行が横にスクロールしていて、盤面からはみだしたらいけない。(英文が読めている気が全くしないくらい長いけれども...。)


動的にグラフが書き変わる状況でダイクストラ。多分、何フレームでループするかを各行について覚えておいて、そのタイミングで入れるかどうかとかを計算しつつ、BFSみたいな感じで最初に到達するのを求めて、ダメだったらおしまい、という感じにやればいいんだろうと思う。要はDPなんじゃないかなぁと。ループの長さによっては単純にやるとTLEするのが目に見えている。


こういうのってやる気出ないなぁ。書き始めても解ける気が全くしないだろうし。凄い解法が浮かばないとやらないと思う。そもそも1時間で解けないだろうに...。