問題リンク Doctor's Research Rooms 解法 （部屋の番号を0〜n-1と考えています。） 幅優先探索＋経路記憶の問題です。ここでいう経路は通った道筋だけでなく、スイッチのON, OFFのことも含みます。 部屋は高々15個なので、部屋の照明の状態と今いる部屋の対…

問題リンク Dice Puzzle 解法 全探索＋枝刈りで解きました。 サイコロの状態数は24なので全状態数はざっと24^8だけあります。 サイコロを隣接して置くための条件が厳しいのでバサバサ枝刈りしてスピードアップさせます。 汚くて冗長なコードを書いてしまいま…

問題リンク Lunch 解法 全探索の方針でいきます。10! = 3*10^6くらいなので枝刈りできればまぁ大丈夫でしょう。 お弁当を積み重ねていくわけですが、上の段から考えていきます。 そうでないと、あるお弁当がつぶれないかどうかの判定が積み重ねの途中ででき…

問題リンク Blackjack 解法 手持ちのカードの枚数が分からないので、nextLine()で読み込んで" "(空白)でsplitする必要があります。 エースが1にも11にも使える点が厄介なところです。 そこでi枚目までのカードを使って表現できる数字にマークをつけることに…

問題リンク Kannondou 解法 DPが使える問題です。 dp[i][j]: i回階段を上がってj段目にいる上がり方の個数 とすると、i歩目でj段目にいくことができる上がり方はi-1歩目にj-1, j-2, j-3段目にいるときなので、これらの和がdp[i][j]になります。 n段目への上…

問題リンク Bubble Sort 解法 バブルソートのアルゴリズムが書かれているのでその通りに実装して、スワップ回数を数えるだけです。 ソース

問題リンク Area of Polygon 解法 円の半径は1だと決めてしまいましょう。多角形の面積はm個の三角形の面積の和となります。 角度θが与えられたときの三角形の面積Sは S = (1*1*sinθ)/2 = (sinθ)/2 となります。ただ、この問題では面積の大きさの比較だけで…

問題リンク Lottery 解法 もの凄く問題が長いので要約してみます。 要約 pとmが与えられます。[p-m, p+m]の区間にある素数の個数(ただし、10^6以上の素数はノーカウント)をXとします。 Xが0のとき、王様へ1プライムが返還され、それ以外のときX-1プライムを…

問題リンク Ohajiki Game 解法 シミュレーション問題です。 とるおはじきの個数が決められているのでその通りに取って、残っているおはじきの個数を出力するだけです。 ソース

問題リンク Highway Toll 解法 まず、距離と料金を頑張って2次元配列で表します。 ICの通過時刻は分で単位を統一した方が都合がいいと思います。 出発時刻と到着時刻のどちらかが17*60+30〜19*60+30の範囲に入っていれば半額対象となります。 また、この問題…

問題リンク Hamming Numbers 解法 整数NがハミングナンバーかどうかはN未満の数全てについてハミングナンバーの真偽が求まっていればすぐ分かります。Nが2の倍数かつN/2がハミングナンバーならば真。3と5についても同様です。また、同時に整数Nまでのハミン…

問題リンク Sport Meet 解法 チームを表すクラスを作り、タイムでソートできるようにしてあります。タイムは分と秒で来るので、秒で揃えたほうが楽です。 ソース

問題リンク Delivery Fee 解法 やるだけ問題です。配列を使ったので少しはスッキリしています。 ソース

問題リンク The Best Body 解法 やるだけ問題です。 ソース

問題リンク Collatz's Problem 解法 整数nが計算により1にたどり着くまでの回数は当然変わらないのでメモ化をしました。 ソース

問題リンク Russian Dolls 解法 人形を頂点としたとき、人形iの中に人形jを入れることができるならばiからjへ有向辺を引きます。マトリョーシカの性質から、閉路ができることはあり得ません。するとこれは DAGになります。このグラフ上のパスの長さがすなわ…

問題リンク Moats around the Castle 解法 少し特殊な最短路問題と考えることができます。dist[i][j]を(i, j)までの最短距離として考えてたものを(i, j)にたどり着くまでに堀から上がる最小回数とすることができます。また、忍者はグリッドの周りのどこから…

問題リンク Spider Jin 解法 最短路問題です。 ビルをノードとして、距離Rが50以下であるような2つのビルi, jの間にコストRの辺を張り、あとはダイクストラです。 ビルsからtへ辿りつける場合、最短経路がユニークに決まることが保証されており、この問題は…

問題リンク Sum of Cards 解法 部分問題に落とせます。 dp[i][N]: i番目までの種類のカードを使って、数Nを実現する組み合わせ数 カードiの番号がvだとするとi番目のカードを使うことで新たに数Nを表現する方法はdp[i-1][N-v]通り増えます。 ソース

問題リンク Triangle and Circle 解法 線分と点の距離が使いこなせればいける幾何問題です。 まずB(三角形が円内に収まる)を調べます。円の中心と、三角形の頂点との距離が全てR以下ならBです。 次に円の中心が三角形の内部にあるかどうかと、三角形の各辺と…

問題リンク Bowling 解法 ガチ実装問題です。倒ピン数が与えられ、スコアを計算します。何フレーム目の何投目の倒ピン数かを管理しなければならず厄介です。10フレーム目で3投目があるかどうかも気をつけてチェックします。 自分は入力時点で得点を計算する…

問題リンク Grid 解法 数えるだけ問題です。数える方法は色々あると思いますが、今回は上下左右方向はfor文で、斜めは再帰でという割と謎な解き方をしています。 ソース

問題リンク Twin Prime 解法 エラトステネスの篩を作ります。 Nが大した大きさじゃないので、Nから数を下げていき、NとN-2が共に素数であるようなものを見つければいいです。 ソース

問題リンク Eye Test 解法 数えるだけです。 ソース

問題リンク Candy and Class Flag 解法 1〜39の学生番号を0〜38だと思えばN%39の番号の学生がクラス旗を持ちます。 N%39は実際の学生番号と1ずれているので1を加えます。 ソース

問題リンク Fukushimaken 解法 基本的にはシミュレートするだけです。 w[i]はi番目のグループの食事時間です。 c[17]配列がカウンターの状態を表しています。要素が0ならば空席を意味し、そうでなければ残りc[i]分でそのカウンターが空くことを意味します。 …

問題リンク Cards 解法 山を重ねるとき、隣り合った者同士で重ねるので部分問題に落とすことができます。 dp[i][j]: i番目からj番目の山を1つにするのにかかる最小コスト このDP表をiとjの幅wが小さい方から埋めていきます。 基底 dp[i][i](0 ソース

問題リンク Packet Transportation 解法 ルータをノードしたネットワーク上で幅優先探索します。 始点から終点に行くまでに訪れたルータの個数がTTL以下ならば到達することができます。 ソース

問題リンク Altair and Vega 解法 遮断は牽牛と織姫のどちらか一方のみが三角形の内部にあることをいいます。 牽牛と織姫それぞれについて三角形の中にいるか調べ、その結果の真偽が互いに異なればOKとなります。 三角形の中に点があるかどうかは、辺を向き…

問題リンク Nature of Prime Numbers 解法 初めに2乗をnで割った余りとして出てくる数をリストアップします。 リストアップしたものの中から2個を選んで差の計算をし、カウントします。 ソース