問題 0~Nまでの盤面がある双六をします。 ダイスは1~6で、確率はすべて等しいです。 スタートは0で、ゴールがNです。 ゴールを通過すると、溢れた分だけ戻ります(ゴール扱いにはなりません)。 特殊マスが2種類あり、 L : 一回休み B: スタートへ戻る という…

問題 解法 この解法はばたこ(@btk15049)さんから聞いたものになります。 dp[i] = i番目の単語までで、消去できる単語数の最大値 とします。 すると、i番目の単語を利用して、それより前の単語を消すかどうかの2パターンにまず分かれます。 i番目の単語を利用…

問題 提出コード 数ヶ月放置してから考察しなおしたらすんなりいきました。 解説がなくてわからない問題は寝かせるのも大事だと思います。 解法 まず、サンプルケースなどを利用して手元で計算すると、 (縦における原点からの距離×縦の辺の長さ、の総和)×(横…

問題 橋の下をN隻の船がくぐります。船がくぐるには、橋を上げないといけません。 橋を上げる、もしくは下すのには60秒かかります。 船が橋をくぐるのには20秒かかります。 また、船は橋の前に到着してから1800秒(30分)待機することができます。 船が到着す…

問題 提出コード 解法 基本的に、1つのトランプは1回操作するだけで必ず正しい位置に戻せるので、最悪N回の操作が必要になります。 そして、操作の回数を最小にするには、そもそも操作しないトランプの枚数を最大化すればいいことになります。 これはつまり…

問題 与えられた集合から、任意の2つの元が互いに素になっているような部分集合をつくり、最大となる要素数を出力する、というものです。 これをT回繰り返します。 解法 まずはじめに、1はすべて部分集合にいれることができるので、1が入力された回数だけ別…

Differential Pulse Code Modulation 提出コード 差の二乗を最小化したいので、動的計画法を利用します。 とし、入力信号の番目を見るとき、複合化後の出力信号の値がになるような遷移の中で、求めたい値の最小値を記録します。dpの配列は大きな値で初期化し…

Invest Master 提出コード 一見どっから手を付ければいいか悩みますが、わかるとすごくスッキリします。 手数料が何もないので、毎日株をすべて一度手放し換金するものとします。とくに2日以上同じ株を持ち続けるメリットはありません。 そこで、i日目でうま…

Osaki 提出コード 発車時刻と到着時刻のペアを入力しているわけではない上、入力時点ではソートされているわけではないことに注意します。 というわけで、入力を受け取るときは、発車時刻、到着時刻それぞれ別でまとめておき、入力後にそれぞれソートします…

D - 注文の多い高橋商店 提出コード 満点を取るには、ほぼでクエリにこたえていかないといけません。 そこで、 ans[i][j] = i番目の品物を使わずにj個選ぶ方法 とすると、与えられたk、xを用いてans[k][m-x]を参照するだけで答えを出すことができます。 まず…

蟻本に載っている重複組み合わせの式変形がピンとこなかったので、頭の整理をするためにメモを。 問題 種類の品物が存在し、番目の品物が個あるとき、これらの中から個選ぶ組み合わせの総数を求めよ、というものになります。 解法 まずはの解法からです。 番…

問題 提出コード ほとんど自力で解けたのでなかなかではないかなーと思ってます！ 問題の制限より、頂点の番号が大きい方から順番に見ていくと、そのとき見ている頂点は必ず木の根になっています。 なので、番号が大きい方から順番に、そこを根とする部分木…

競プロの練習会で、こちらのセットを使用したバチャコンをチームで行ったので解いた問題についてのメモをしていきます。 チームメイトはICPC出場時と同じくやまさん(@yamasangamasan)、べるくん(@dora_marutation)でした。加えて、相手チームがICPC本戦出場…

JOI 2012-2013 予選 問題４ 提出コード 動的計画法を使うことを考えます。 まず、dp[i][j]として、j日目にi番目の服を着たときの、1~j日までの、「派手さの差の絶対値」の合計の最大値、とすると、 dp[i][j]=max(dp[k][j-1]+k番目の服とj番目の服の差の絶対…

500-yen Saving | Aizu Online Judge 提出コード 最終的な目標は、 ➀ 500円玉の枚数をできるだけ多くする ➁ ➀の中で、購入額を最小にする という二つなので、これを評価値として動的計画法を利用します。 動的計画法をする前に、少しだけ考察をします。 ある…

コンテスト開始2分前ぐらいまでアイスを食べていて、乗り遅れそうになりました。 A - F 提出コード if文を使って、aとbの足し算、掛け算が15になるかどうかを調べます。どちらでもなければその時用の出力をして終わりです。 B - Acrostic 提出コード 入力用…

今回は、自分の大学の講義で数日前に扱われた有名な動的計画法の問題、ナップサック問題についてのプログラミングの解説をC言語でしてみようと思います。 理由は、講義の説明だとわかりづらいなと思ったからです。ただ、この解説をするのはとても難しいと思…

ABC100の一歩手前になりました。自分はABC88から参加し始めたのでまだ日は浅いですが、100回になっても今まで通り頑張っていこうと思います。 さて、前回のABCですが、久しぶりにD問題が解けてかなり嬉しかったです。ただ噂のC問題が解けず全完には至ってな…