481.1

かなり嫌いな落とし穴に毎回はまってる...。

250

ある問題の答えについて、Lie人に嘘を教えた状況で、N人のうちYes人がYesと聞いたと教えてくれた。実はLiar人が嘘をついたという状況で、もとの問題の答えはどっちだったか答えよ、という問題。曖昧か、矛盾という状態もある。

要はYes人とNo人からLiar人移動させるというのを可能な限り全部試して、Yesな人がLie人かNoな人がLie人になれば、その逆が正解ということになる。面倒なだけの問題。

500

ジョブを投入した人の名前とそれにかかる時間のリストが与えられる。ある人のジョブ(複数あり得る)が全部終わるまでの時間を考えて、その平均値が最小になるようなアルゴリズムでジョブを一つずつ消化する。同じ値になるものが複数ある場合は等確率。このとき、すべてのジョブについて、終了する時間の平均値を求めよ、という問題。

自分よりもジョブの総時間が短い人は常に先にやられる。同じ人は等確率で先にやられる。自分のジョブの中はどれも等確率。というのを単純に計算するだけ。問題は意味もなくint溢れを起こすといういやらしさ...。

900

一直線上に配置されているプリンタがある。プリンタはそれぞれある初期値を持っていて、目的の値を指定すると、それを印刷するのに、差分の絶対値+1秒だけかかる。プリンタへの指示は一瞬でできるとして、すべてのプリンタを利用して、目的の値をすべて印刷したい。このときの最小時間を求めよ、という問題。

取り敢えず、あるプリンタに指示を送る場合、途中のプリンタに指示を送らずに通るということはない。(既に指示していれば何もしないが。)なので、今の位置が分かれば、どのプリンタに指示を出したか分かる。後は何を既に指示として与えたかを覚えておく。そうすると、現在の状態から残りのプリンタ群にどういう指示を送れば最適化というのは常に変わらないので、それをメモしながら探索していく。最後に戻ってきたらそれが答えになっている。