問題リンク Butterfly 概要 後回し 解法 時間が[6〜22]の17通りしかないのでビットを立てることで2^17までの整数で時間帯を表現することができます。 デートに使う時間は[S, E)という半開区間であることに注意してビットを立てます。 各男性のデートに使う時…

問題リンク Infinity Maze 概要 後回し 解法 u[H][W][D]: (H, W)に向きDで最初に到達したときのステップ数 という表を作って行きます。 10^18もステップがありますが、ボード上の状態は40000しかないので、必ずどこかでループが生じます。 長さKのループに入…

問題リンク Water Clock 解法 水槽クラスを使って実装しました。 水を流しいれる箇所は1か所なので、その場所へfq*tの水を一気に流します。溢れた水を隣接するマスへ流す処理を再帰処理して解きます。いかにミス無く実装できるかがカギとなります。 類題にAO…

問題リンク Farey Sequence 解法 F_iの項数はF_(i-1)の項数に、分母がiのものを加えたものとなります。 iが分母のもので加えるべきものは、分子が分母と互いに素のものである必要があります。つまり、1 包除原理、もしくはオイラーのφ関数によって求めること…

問題リンク Anipero 解法 DPです。dp表をシークレット用とスタンダード用の2つ用意します。 dp[i][x][L]: i番目までのアイドルに対して、費用Lを使ってx人雇う時の最大満足度 とすれば解けます。 この表を2つ作ったら、費用L (L dp_standard[M-1][x][L] + ma…

問題リンク The Legendary Sword 解法 DPです。数字kが書いてあるマス(i, j)に対して、そのマスに到達するまでの最短時間を記録しておきます。 宝珠が1つも無い場合もあるので注意してください。 ソース

問題リンク Seishun 18 Kippu 解法 ワーシャルフロイドで任意の2駅間の最短移動時間を求め、 S→P + P→G が答えとなります。 ソース

問題リンク Problem B 解法 ある人が申請する作業時間は実は一意に決まります。難易度がkの人の申請する作業時間は作業可能時間を超えない最大のkの倍数となります(0でもいい)。 あとは、ルールに従って作問担当者を決めるだけです。 ソース

問題リンク Swap Cipher 解法 暗号化の逆順で復号化するだけです。 ソース

問題リンク Sequence Configuration 解法 ランダムに0と1の列を生成し続ければ解けます(!?) ソース

問題リンク Shiritori 解法 プログラムからは、常に同じアルファベットで終わる単語を発言し続ければ、AIは最大27回までしか正しい返答を返せません。 こちらから投げる単語が不正でないか、AIが不正な答えを返してないかをチェックしながらこれを実装します…

問題リンク Cicada 解法 典型的なDPです。 dp[i][j]: (i, j)からゴールに行くまでに会う蝉の最小数 という表を右下から埋めていくことで解けます。 ソース

問題リンク KUPC 解法 K, U, P, Cの枚数のうち、一番小さいものが答えです。 ソース

問題リンク Pipeline Scheduling 概要 ユニットが5個あり、1つのタスクを処理するための手順表が与えられる。表の長さはNである。 処理を行うクロックに衝突が生じないように10個のタスクを処理するための最小クロック数を答えよ。 N 解法 深さ優先探索+枝刈…