問題リンク 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個を選んで差の計算をし、カウントします。 ソース

問題リンク Spiral Pattern 解法 (i, j)をぬろうとしたとき、(i, j)に隣接するマスが既に'#'だともう塗れないので方向を変えます(自分が来た方向のマスは除く)。方向を変えてもなお、次のマスが塗れなかったらそこで終了です。 移動ベクトルを使えばすっきり…

問題リンク Bus Line 解法 基本方針は幅優先探索による最短路探しです。が、思った以上に面倒な問題です。 遷移先を見極める必要があります。 6-9においては1方向に進むので問題ありません。 0-5の区間は今どちら向きに進んでいるかの向きの情報が必要になり…

問題リンク Snakes 解法 AかBかを判定するメソッドを気合いで作りました。 判定条件を書き下すように書いたので読みづらいと思います。 DFAを定義してゴニョゴニョした方が良かったかもしれません。 ソース

問題リンク Track and Field Competition 解法 クラスTを作りました。Tは選手の番号とタイムを持ち、タイムの昇順にソートできるようにします。 8人で走る組が3つあるので各組についてタイムでソートします。 各組のトップ2は出力し、3,4位を別の配列tに突っ…

問題リンク Middle-Square Method 解法 String s = x+""; とすれば数xを文字列にできます。 sの長さが8未満のとき、先頭に"0"を追加し続ければ長さ8の文字列にできます。 中央4文字を取得するにはs.substring(2, 6)とします。 取得した文字列をInteger.parse…

問題リンク Frequency Distribution of Height 解法 数えるだけです。 ソース

問題リンク Clock Short Hand and Long Hand 解法 時針と分針が何度に傾いているかを調べます。 度に直すことができたらあとは調べるだけです。 ソース

問題リンク Exit Survey 解法 N人の買い物金額の合計をNで割ればいいだけですが、N ソース

問題リンク Rotation of a Pattern 解法 図をs[ ][ ]として、90度右に回転させた図をt[ ][ ]とします。 sからtを得ることができればこれを繰り返すことで180度270度回転の図も得られます。 t[i][j]の画素はs[i'][j']の画素からやってきたもので、これは(i, j…