355.1

お世辞にも良いセットとは言えないが、300はやるべき。

300

濃度と量の分かっている液体がいくつかあるので、欲しい濃度の液体をできるだけたくさん作りたい。作ることのできる最大量を答えよ、という問題。

中途半端に使う可能性がある液体は高々一つなので、濃度順にソートしてやって、全部使う範囲と追加で使うもう一個を全探索する。中途半端に使うヤツの分量は整数で計算しておくと、誤差で失敗しない。(doubleが出ないように除算ではなく乗算を使う。)

600

多次元空間上に4つ点があり、それぞれの間の距離が指定されている。このとき、そのような点配置が可能か否か答えよ、という問題。

多次元と言いつつ、冗長に空間を広げる必要はないので、4点なので高々3次元で十分。まず、二点を固定して、他二点について、三角形が作れるかどうかを吟味する。どちらも可能であれば、その三角形を固定した二点を中心軸として回転させる。そうすると他二点の取り得る距離関係が分かるので、その上限と下限の間に含まれているかどうかを調べるだけ。結局、これら二点は同心円の円周上を移動し、二円の距離と半径が分かるので、最近点は同じ側にあり、最遠点は反対側にある。

900

六角形グリッドの一部がある。隣接するグリッドが六個ある点について、白黒のいずれかを塗るが、白に塗る場合は周りのA個を白く塗り、黒に塗る場合は周りのB個を黒く塗る。このとき、何通りの塗り方が可能か答えよ、という問題。

左上から順番に塗っていく。既に確定させたもので、かつ今後使い得るものの情報を状態にDPするだけ。六角形グリッドなのでめんどくさい。やるだけ。