問題リンク Mr. Rito Post Office 解法 ワーシャルフロイドで下ごしらえしてからDPで解きました。 まず、陸路のみでの移動、海路のみでの移動それぞれについて全頂点間最短距離をワーシャルフロイドで求めます。 次に、以下のようなDPを考えます。 dp[i][j]:…

問題リンク The Melancholy of Thomas Right 解法 列や行は入れ替えても構いません。よって、数字の並びをソートしても構わないことになります。 ここであることに気づきます。以下は行と列をソートした後のサンプル3です。 0 1 1 2 5 5 5 8 8 9 0 1 o 3 o o…

問題リンク Addition Game 解法 気づいたら簡単系の問題です。 少なめの桁数だと全ての通りをシミュレートできるので色々試してみました。すると、どんな取り方をしても勝者が必ず一方にだけ偏りました。そこで、「どんな取り方をしても勝者は変わらない」と…

問題リンク Digits on the Floor 概要 床にN本の線分で書かれたデジタル数字がある。0〜9の数字がいくつずつあるか答えよ。 線分の置かれ方には以下のような制約が保証されている。 線分同士は交差しない 2本の線分が接している時、その角度は直角 ある1点を…

問題リンク True Liars 概要 P1人の正直者とP2人の嘘つきがいる。正直者は常に真実を言って、嘘つきは常に嘘を言う。 P1+P2人のうち、正直者はどの人物達かを特定したい。 X番の人物に問いかけ、「Y番の人は正直者か」という質問をN回する。X番の人物の返答…

問題リンク Chain-Confined Path 解法 ダイクストラで解きました。 頂点は両端の円の中心と、円の交点たちです。 面倒なのが、点Pと点Qの線分全体が円の内部にあるかという判定です。 図を見ると、円の内部を通るような線分は、2つの交点の間を通っています…

問題リンク Village 解法 村をx座標の昇順にソートして、[x-R, x+R]の範囲にある全ての村と距離比較をするというのが方針です。 まず、全ての村の対について距離がR以下か、3R以上という制約があるので、[x-R, x+R]の範囲以外でこれらと同じ表札になる村は絶…

問題リンク Alien's Counting 概要 指がN本あるエイリアンがいる。人間が指を折って数を数えるようにエイリアンも指を折って数を数える。エイリアンにはM個の指を折るルールがある。ルールは2つの整数A、Bで与えられ、Aを折ると常にBも同時に折れることを表…

問題リンク Save your cat 概要 N本の柱が平面上に立っている。更に、柱を端点とするM個の壁がある。 壁で囲まれている内部には必ず猫がいて、壁を壊すことで猫を外に逃がしたい。 壁を壊すには、壁の長さだけコストがかかる。 猫を全て逃がすために必要な最…