問題リンク Reading a Chord 概要 M個のトーンからなる音がなるようなコードを全て列挙せよ。ただし、各トーンのオクターブの高さは考慮しなくてよい。 コードは図1にある通りである。 コードに任意のテンションをつけることができる。例えば、(-9)というテ…

問題リンク Sort the Panels 概要 N個の'W'と'B'からなるパネルの順列S, Tが与えられる。次のルールに従ってSをTへ変化させるのにかかるコストを最小化せよ。 機械が1台ある。機械は任意のパネルへ移動してマークをつける。続けてもう1か所別のパネルへ移動…

問題リンク 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 解法 深さ優先探索+枝刈…

問題リンク Differential Pulse Code Modulation 解法 DPです。 dp[i][x]: i番目の信号を数xで復号化したときの最小値 という表を作れば解けます。配列が2本あれば十分です。 ソース

問題リンク Moonlight Farm 解法 収入: F*S*M-P 時間: A+B+C+(D+E)*M 変数が沢山ありますが要はこういうことです。 ソース

問題リンク Sum of Consecutive Integers 解法 連続する列の先頭の数字を決めて、和をとってみるだけです。 ソース

問題リンク A Book Shop With a Frequent Greetings 解法 シミュレート問題です。 店員iに時間tに唱和を開始させるというイベントを管理します。 各店員には最後に唱和を終了した時刻last[i]を持たせます。 (i, t)のイベントが発生したとき、店員iが唱和する…

問題リンク Unit Converter 解法 数値を文字列Tと見なします。Tから'.'を除いておきます。 0でない数値が初めて出現するインデックスをkとすると、有効数字KはT.length - kとなります。 また、pを小数点が右側につく桁のインデックスだとします(入力に小数点…

問題リンク Mirror Cave 解法 (Linの位置, Renの位置)をノードにした幅優先探索で解けます。状態数は50^4なのでメモリもなんとか大丈夫です。 どちらか一方だけがゴールを踏んだ場合、それから先の状態を探索してはならないということに注意してBFSを書くだ…

問題リンク Restrictive Filesystem 解法 区間の集合の管理を頑張る問題です。 空いているセクタの区間の集合をL、識別子kの区間の集合をL_kとします。 コマンドRのとき、全てのL_kの中にセクタ番号を含むものがあるかを探します。 コマンドWのとき、Lの先頭…

問題リンク Brave Princess Revisited 解法 (町, 残金)をノードにしたダイクストラで解けます。 (i, c)の状態からはお金を払わずに行く進み方 (残金が距離以上あるとき)お金を払って襲われる人数を0にして進む方法の2通りがあります。 ソース

問題リンク Matsuzaki Number 解法 Nより大きな素数の組み合わせの和を十分多く求めてその中でP番目の大きさのものを探す方針です。 大きさ150000程度までの素数を求めておきます(150000は適当です)。 Nより大きい最小の素数がk番目の素数だとします。k 〜 k…

問題リンク The House of Huge Family 解法 まず、入力の制約の「Yiは重複しない」に注目すると辺の数は高々N個だと分かります。さらに、負の重みを持つ辺は取り除いた方が絶対得なので無条件で取り除くことにします。 問題の条件を満たす家の構造を考えたと…

問題リンク Osaki 解法 イベント処理で解きました。 時刻の昇順でソートし、時刻が出発のものだったら電車の車両が増えるのでインクリメント、到着のものだったらデクリメントします。このシミュレート中の車両の最大値が答えです。また、出発の時刻と到着の…

問題リンク Heian-Kyo Walking 解法 非常に典型的なDPになります。 ホクサイはゴールから遠ざかるような動きをしないので(i, j)の交差点から(i+1, j)か(i, j+1)に進みます。 dp[i][j]: 交差点(i, j)に到達する経路の数 とすることで解けます。 ソース

問題リンク Petting Cats 解法 長方形[x, x+w]*[y, y+h]の上に猫が何匹いるかを数えます。 ソース

問題リンク Luck Manipulator 解法 最大10000フレームまでシミュレートします。 ソース