2011-09-30から1日間の記事一覧
問題リンク 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 ソース