問題 問題概要 省略 解法 forで回す。 ミス 特になし。 コード #include <iostream> #include <cstring> using namespace std; int main(void){ string s, ans; cin >> s; for (int i = s.size() - 1; i >= 0; --i){ if(s[i] == '>') ans += '<'; else ans += '>'; } cout << an</cstring></iostream>…

問題 問題概要 チェビシェフ距離の最大のものを探す 解法 表を左上から右下へ、右下から左上へ、右上から左下へ、左下から右上へチェビシェフ距離を動的計画法で埋めていった。例えば、左上から右下へ埋めていく場合を考えると、現在見ているマスの左下、左…

問題 問題概要 数字の一か所を入れ替えて、最も大きい数字を求める。 解法 数字を文字として扱う。文字列の一か所を入れ替えたものを全探索している。出来上がった文字列をstring型のvector配列にいれて、ソートする。数字だけじゃなくて、文字列もソートで…

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

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

問題 問題概要 省略 解法 ハッシュて書いてあるけど、特に知識などはいらず、ハッシュ生成の作業を実装するだけ。素数判定の部分にエラトステネスを使ってる。 またハッシュ生成後は1ケタの数字となるので、生成後の数字は多くても0~9の10通りに絞られるん。…

問題 問題概要 省略。 解法 dp[i番目までのおもりを見た時][左側の重さj] := (trueならある)というbool型の配列を用意して、i番目のおもりの時に、左側の重さがjが存在するかをdpで探索していく。単純におもりが左の天秤なのか右の天秤なのかでやってしまう…

問題 問題概要 省略。 解法 エラトステネスをイメージしてやった。アルゴリズムは幅優先探索を利用している。queueにスタート時点の1をいれて、そのあとは、2進数にした時の1の数によって、両側に動いた場所を調べている。幅優先探索で調べると、移動が少な…

問題 問題概要 複数山の石取りゲーム 解法 まず、素因数分解をします。そして、同じ素因数の数を数える。素因数の因数のどおしをxorで計算する。すべての素因数に対してその処理を行い、その結果が0であれば、後攻の人がかつ。この問題は必勝法が存在するの…

問題 問題概要 省略 解法 この問題は町どおしを有向グラフでつないでおり、現在の町の番号は増える方向に必ず増えるように条件が与えられている。そして、残り残金も減る方向に行くので、この問題はDAGグラフで考えることができ、dpで解くことが出来る。 dp[…

問題 問題概要 門松列をぶち壊す。 解法 何回でも並び替えていいので、昇順または降順に並び替えてしまえば、大丈夫。バブルソートで実装した。 ミス なし。 コード #include <iostream> #include <algorithm> #include <vector> #include <cstdio> using namespace std; typedef long long ll; ty</cstdio></vector></algorithm></iostream>…

問題 問題概要 省略 解法 2m個で循環するので、mod(2m)で計算してる。modを取った後の値がmより大きいか、小さいかで場合分けして、数字が昇順に並ぶ部分なのか、昇順に並ぶ部分なのかで考えて、何組なのかを考えている。 ミス 1オリジンでやっていてばぐら…

問題 問題概要 省略 解法 X進数で表した時17となるXを求める。17の1が数字X分の大きさを持つので、X + 7 = nより X = n - 7を解答として出力すればいい。ただし、17ということは少なくとも８進数以上であることを意味する。X = 8のときn = 15より、nが15より…

問題 問題概要 省略 解法 ソートしてやるだけ。ソートして１番目のものと最後のものを除いた和をだし、それを４で割って平均を出している。 ミス 小数点第２位まで。。 コード #include <iostream> #include <algorithm> #include <vector>> #include <cstdio> using namespace std; #define all(v</cstdio></vector></algorithm></iostream>…

問題 問題概要 完全２分木上をどのようにたどれば、ルートから指定された場所に移動できるかを求める問題。 解法 完全２分木問題は1オリジンにで考えると、配列を使い親と左子、右子を簡単にたどれる。 今回はそこまで考える必要はない。単に奇数なのか偶数…

問題 問題概要 省略 解法 星1だし単純な規則性がありそう。少し実験したら、2回目にキャラクターを利用した時が最大になりそうなことが分かった。数学で証明できると思いますが、わかりません。 ミス なし コード #include <iostream> #include <cstdio> #include <algorithm> using names</algorithm></cstdio></iostream>…

問題 問題概要 カップ麺を買う。買っていく途中で所持金が素数になるとはじめの所持金に戻ることができる。ただし、1つの素数につき、1度だけしか戻ることはできない。最大でいくつのカップ麺を買うことができるかを求める。 解法 まず、所持金以下の数字の…

問題 問題概要 共通部分文字列の問題。ただし、連続した文字列でなければならない 解法 単純なdp。文字列s1とs2の両方を何文字目ま見ているかという要素を配列の要素と持つdpを考えればいい。 dp[i][j] = dp[s1のi文字目までで考える][s2のj文字目までで考え…

問題 問題概要 二本の竹がある。二本の竹から任意に注文された竹の長さを切る。多くの注文に答えられるように切るとき、最大いくつの注文に答えられるかを求める問題。 解法 まず注文された竹の長さを昇順にする。竹が短いものから注文に答えていくのは貪欲…