問題リンク Immortal Jewels 解法 答えとなる直線があったとします。この直線を、吸着できる宝石の数を変えないように動かしたとき、それ以上動かせなくなる境界的な置き方が存在します。その直線は、2つの宝石と、磁力の強さだけ半径を増やした2円、これら…

問題リンク The Number of the Real Roots of a Cubic Equation 解法 f(x)を微分してみる問題です。 f(x)を微分したf'(x)は2次方程式になり、その解がf(x)における極値を取る座標になります。極値と極値の間の区間は、ただの単調増加(減少)な関数になるので…

問題リンク 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…

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

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

問題リンク Quest of Merchant 解法 市場から街をぐるっと巡って帰ってくるので、1回目の仕入れと2回目の仕入れは互いに影響しません。よってDPの形にできそうだと考えました。 dp[T]: 残り時間Tを使って得られる最大利益 1回の仕入れで同じ街に2回訪れるの…

問題リンク Rectangular Stamps 解法 幅優先探索で解きました。 スタンプを押す順番をそのまま考えると状態数がえらいことになりますが、押す順番の逆を考えると状態数が減ります。各マスに対して、まだスタンプを押していない場所をビットで覚えておきます…

問題リンク Starting Line 解法 シミュレーションのような感じで解きました。 人参に関して言えることは、 加速状態にない場合、すぐ食べたほうが良い。既に加速状態の場合、人参は所持したほうが良い。ただし、人参が既にK本ある場合はその場で食べたほうが…

問題リンク Programming Contest Challenge Book 解法 探索+枝刈りが方針です。 3本の棒A, B, C (A A+B の三角不等式を満たすかを調べればOKです。 色々ノートで思考していると、1個目の三角形で使う棒を決めると、2個目の三角形で周辺の和が最大になるよう…

問題リンク Merry Christmas 概要 N個の家、M本の双方向の道からなる街がある。 更に、L個のクリスマスプレゼントのリクエストがある。リクエストiは{pi, ti}からなり、時刻tiちょうどに家piにプレゼントを配るという意味である。 プレゼントを運ぶためにサ…

問題リンク Road Construction 概要 N個の街がある。街は1〜Nで番号付けされていて1番の街は首都である。 国王が街同士を結ぶ街道をM本作ろうと計画している。街道は双方向で、街iと街jを結び、その距離はd、建設費用はcである。以下の条件を満たすようにM本…

問題リンク Usaneko Matrix 解法 各行、各列、＼のライン、／のライン上に登場した数字の数を記録します。各ライン上のカウントがnになったら「直線状に並んでいるもの」が1つできたことになります。 注意としてこの方法だと、n=1のとき、カードの数字xが登…

問題リンク Ennichi 解法 ストレートにシミュレートするだけで解けます。 ブロックの落下処理を行った後、最下段にブロックがあるかチェックすればクリアの判定ができます。 ソース

問題リンク Kaeru Jump 概要 H*Wの大きさの池に葉っぱと1匹のカエルがいる。カエルは上下左右へ飛ぶ方向を決めたら、その方向の一番近い葉っぱに飛ぶ。このとき、飛ぶ前に乗っていた葉っぱは消えてなくなる。また、カエルは自分が向いている方向の真反対の方…

問題リンク UTF-8 解法 DPです。 dp[i][j]: iバイト目をjバイト文字の先頭と解釈したときのiバイト目以降の解釈の組み合わせ数 という表を後ろのバイトから埋めていけば解けます。 iバイト目をjバイト文字と解釈する方法を説明します。 まず、マスクが0や1の…

問題リンク KULASIS 解法 DPです。形はかなり複雑になりました。 あるボタンは0〜3回押す場合を考えれば十分です。4回以上押す場合を考えるのは無駄です。 すると、i段目のボタンについてボタンの押し方は4^4 = 256通りあることになります。 i段目のボタンの…

問題リンク Carrot Tour 解法 基本的な方針はDPです。向きとその角度という移動制約があるため、直前にどこの都市にいたかも情報として必要になります。 dp[i][j][k]: 直前に居た都市がjで都市iを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の枚数のうち、一番小さいものが答えです。 ソース