問題 問題概要 縦横のマスが与えられる。その中に壁が含まれていて、それらを爆弾で吹き飛ばす。爆弾の効果は、爆弾を置いた列と行のすべての爆弾を吹き飛ばす。 解法 まず、列と行ごとに壁の数をメモしておく。これをしないで、毎回調べるとTLE。また、すべ…

問題 問題概要 粒子の数字(座標)とそれに対応するLRのどちらかが与えられる。Lの場合、その座標から左に動かすことができ、Rの場合、その座標から右に動かすことができる。粒子が1秒で1マス分、指定された 方向に動くことができる。最短何秒でぶつかるか。ま…

問題 問題概要 サイコロを降って、目の合計がK以上になるサイコロを振る回数の期待値を求める問題。 解法 漸化式を用いて動的計画法で解く。 ミス 漸化式をすこし間違えた。dp[i] := (これまでの目の合計が i のとき、合計が k になるまでに降ることになる回…

問題 問題概要 文字列を数式ととらえて、計算していく、構文解析の問題。 解法 *,+が出てくるまで、いくつ数字が並んでいるかを確認した後、数字の並びの前に出ていた記号によって、数字を足すのか、かけるのかの処理を行えばいい。ただ、実装が少しめんどく…

問題 問題概要 文字列の中で最も左のもの、またはもっとも右の文字を任意の順番で取り出していき、取り出した順番で並べる。何種類の文字列が作れるか。 解法 全探索する。左または右から取る順番をbitを用いて実装した。今回はbit列iのpos番目のbitが立って…

問題 問題概要 省略 解法 dp問題。 ミス オーバーフローに注意。dp[何番目の変数か][合計値] := (整数の組みの個数) とおく。変数を一つずつ増やしてみていく。漸化式はdp[i][j] += dp[i - 1]=%20k">j - kとなる。それぞれの変数は0からnまでとるので、kを0…

問題 問題概要 省略 解法 bitDP。どの商品をすでに購入したかを示す集合を要素として持ち、dpをすればいい。集合が決まっている時の、支払う金額の最小値を求めておけば、その集合内でどの順番で商品を買ったかは関係ないので、dpで解ける。 dp[mask] := (ma…

問題 問題概要 省略 解法 誤差を全く許さない問題。このような時は整数型で計算する。そのためには、1.08倍をするのではなく、108倍をすればいい。ここで100で割るのではなく、下から２桁目に小数点をつけて表示すればいい。 ミス 特になし。 コード #includ…

問題 問題概要 省略 解法 多く進んでもいいのだから、割り切れればそのままでいいし、割り切れなければ、+1すればいいことになる。 ミス 特になし。 コード #include <iostream> using namespace std; int main(void){ int a, b; cin >> a >> b; int ans = b / a; if(b</iostream>…

問題 問題概要 省略 解法 簡単に漸化式がたつ、dp。dp[i] := (iマスに行く方法のパターン)とおくと、漸化式は、dp[i] = dp[i - 1] + dp[i - 2]となる。これは、iマス目に行くには、i-1マス目から1で進む、または i-2マス目から2で進むのどちらかであるっこと…

問題 問題概要 省略 解法 まず、任意の２点間の距離の最小値を求めておく。その後、滞在する２点を全探索で全て調べる。 全探索で dist[0][i] + dist[i][j] + dist[j][n - 1] + s[i] + s[j] の最小値を求めればいい。 ミス 特になし。 コード #include <iostream> #inc</iostream>…

問題 問題概要 省略 解法 少し、考えると、平均を最大にするのは、最も大きいものが１つだけ含まれる集合であり、平均を最小にするのは、最も小さいものが１つだけ含まれる集合のときである。 ミス 特になし。 コード #include <iostream> #include <algorithm> #include <vector> using n</vector></algorithm></iostream>…

問題 問題概要 省略 解法 まず、マークが同じで数字が異なる組み合わせをいくつあるか求める。方法はそれぞれのマークごとにいくつの数字が手札にあるかを調べることで求められる。 次に、数字が同じでマークが異なる組み合わせがいくつあるかを求める。方法…