問題 atcoder.jp 問題概要 N問の問題があるコンテストがあり、i問目(1-index)の問題の配点は p[i-1]点である。この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。 解法 dp[i][j] : i番目まで見て…

問題 atcoder.jp 問題概要 N段の直角三角形状の数列が与えられる。 例) 7 2 3 1 5 4 頂点からスタートして真下もしくは右下に行くことが出来る。底辺までたどり着いたときに経路中の数値の合計の最大値を求めよ。 上の例だと7+3+5=15 解法 上からi番目、左か…

問題 atcoder.jp 問題概要 N枚のカードがあり、i番目(1-index)のカードには整数x[i-1]が書かれている。 何枚かカードを選びカードの整数の平均がAとなるようにしたい。そのような選び方は何通りあるか。 解法 平均を平均のまま扱うのは大変なので合計と個数…

問題 atcoder.jp 問題概要 コインがN枚あり、i番目(1-index)のコインの表が出る確率がp[i-1]、裏が出る確率が1-p[i-1]である。 N枚のコインを投げたとき、表の個数が裏の個数を上回る確率を求めよ。 解法 dp[i][j] : i番目(1-index)のコインまで投げたときに…

問題 atcoder.jp 問題概要 薬品がN個あり、i個目の薬品はタイプAの薬品をa[i-1]グラム、タイプBの薬品をb[i-1]グラム含み、価格はc[i-1]である。 これらの薬品のうちからいくつか選んで混合し、タイプAとタイプBの薬品の混合比がMa:Mbとなるようにしたときの…

問題 atcoder.jp 問題概要 ナップサック問題に言い換える。品物がN個ありi番目(1-index)の重さはA[i-1]、価値はB[i-1]である。 重さがWを超えず、個数がKを超えないように選ぶとき、価値の合計の最大値を求めよ。 解法 個数制限がない場合は普通のナップサッ…

問題 atcoder.jp 問題概要 N個の品物があり、i番目(1-index)の品物の品物の重さはw[i-1]で、価値はv[i-1]である。 品物を重さの合計がWを超えないように選ぶとき価値の総和の最大値を求めよ。 解法 ナップサックDPである。dp[i][j] : i番目まで見て重さの合…

ソート済みのvector Aに対してhoge以上の最小の要素のイテレータ lower_bound(A.begin(), A.end(), hoge)hogeを超える最小の要素のイテレータ upper_bound(A.begin(), A.end(),hoge) 値がhoge以上の要素の個数 A.end() - lower_bound(A.begin(), A.end(), ho…

二次元累積和とは このような配列を考える。これを配列Aとする。配列Aの中の任意の長方形の区間の総和を求めたいとする。 例 図の水色のマスの合計は、1+5+2+6+3+9+3+8=37である。 これは、A[1][2]からA[2][5]までの総和といえる。 これをΣ([1][2],[2][5])と…

グリッド グリッド上のBFS(最短経路) //各点のスタートからの距離を配列で返す //si,sj:スタートの座標 //スタートは壁ではない //辿り着けない:-1 vector<vector<int>>bfs_grid_pass(int si,int sj, vector<vector<char>>field) { vector<int>di; di = { 0,1,0,-1 }; vector<int>dj; dj = { 1,0</int></int></vector<char></vector<int>…

(1)N個の0,1から成る2^N個の配列を生成 int N; cin >> N; for (int S = 0; S < 1 << N; S++) { //作成 vector<int>A; rep(i, N) { A.push_back(S >> i & 1); } //操作 rep(i, N) { cout << A[i] << ' '; } cout << endl; }入力例 3 出力例 0 0 0 1 0 0 0 1 0 1 1 </int>…

(1)問題 atcoder.jp (2)問題概要 1からNまでの番号がついたN頂点の木Gが与えられる。Gの辺を何色かで塗り分ける。一つの頂点から出る辺は全て違う色にするとき最小で何色で塗り分けられるかを求め、塗り方を一つ構築せよ。 (3)前提知識 ・N頂点の木の辺の数…

Union-Find木の書き方、使い方をまとめたUnion-Find木は、以下のことができるデータ構造である。1, 要素aと要素bのグループを併合する。 2, 要素aと要素bが同じグループに入っているか判定する。 (1)書き方 main関数の上に次のように書く class UnionFindTre…

最短経路問題におけるグラフの表現方法、BFS、ダイクストラ法、ベルマンフォード法、ワ―シャルフロイド法についてまとめた。 (1)グラフの表現方法 (1)-[1]重みなしグラフ 重みなしグラフとは、グラフの辺の重みがすべて1のグラフである。 (1)-[1]- 隣接リス…

値の追加、削除が高速にできるlistというSTLライブラリがあるらしいので使い方をまとめた。まずはlistヘッダをincludeする。 #include<list> (1)宣言 「listリスト名」で宣言する。 [例]Aという名前のint型のlistを作る。 list<int>A; (2)末尾に値を追加 「リスト名.pus</int></list>…

問題 https://atcoder.jp/contests/arc004/tasks/arc004_2 <問題概要> 平面上に0～N番のN+1個の点がある。i番目の点とi+1番目の点の距離はd[i]である。0番目の点とN番目の点の距離の最大値と最小値を求めよ。 <問題読み替え> N個の棒がある。これらをつなげ…

整数を文字列として受け取って文字列のまま計算する関数を作りました。 これによってオーバーフローの心配がなくなります。 <1>足し算 <2>大小比較 <3>差 <4>掛け算 割り算と余りの計算はできたら追加します。