Problem - C - Codeforces 問題 大きさ の整数配列 が与えられる。 「の値を任意の値に変更することができる」 という条件下で、 から それぞれの値の出現数の最小値を最大化させたい。 最大化させた出現数の最小値 / この時の最小変更回数 / 変更後の配列 …

TopCoder Statistics - Problem Statement 問題 花の種類を表す文字列 と ある位置における配置禁止の色 の二つの情報が与えられる。 花は色を持ちアルファベットで表現される。 与えられた花を以下の条件に従い並び替えた時、 そのパターンの総数を求めよ。…

問題 B: 花束 - AtCoder Regular Contest 050 | AtCoder 解法 片方の色の花束をいくつ作るか決めた時に、作ることのできる花束の総数が凸関数になる。 よって片方の色の花をいくつ作るかについて三分探索をすればよい。 三分探索については以下の記事が参考…

http://codeforces.com/contest/553/problem/A 問題 1〜kまでナンバリングされたボールがそれぞれ個与えらえる。 これらのボールを全て並べたとき、color(i)の中で右端に存在するボールよりも右側に color(1)〜color(i-1)が存在しないような並べ方が何通りあ…

Problem - D - Codeforces 問題 ツボの中に重複のない番号の書かれたボールがn個入っている。 Andrewと Jerryはこのツボの中から同時にボールを一つだけ無作為に選びとり、 番号の大きい方が勝者となる。(選んだボールはツボにまた戻す) このゲームを3回連続…

Problem - C - Codeforces 問題 n回クエリが投げられる。(各クエリはLとRからなる) L〜R間の整数で、bitの立っている数が最大となるような最小の値を求めよ。 解法 Rの上限がと大きいため、LからRへ値を1ずつ増やしながら 範囲内全ての値のbitをカウントする…

http://codeforces.com/contest/448/problem/D 問題 n * mの二次元テーブルが与えられる。 i行j列目の値はi * jと定義される。 このテーブルの内、k番目に大きい要素を答えよ。 例えば、n=2, m=3の場合テーブルは以下の図のようになり、 k=4 の時、その答え…

Problem - D - Codeforces 問題 大きさ n の整数配列が与えられる。 その後 q 回、クエリxが投げられる。 各クエリごとに、区間の gcd が x となるような候補がいくつあるか答えよ。 解法 nが大きいためとなるような区間の全探索をすることはできない。 解法…

Problem - C - Codeforces 問題 大きさnの整数配列pが与えられる。 この配列の内、重複しない大きさmの区間をk個選択した時の合計値を最大化させたい。 解法 動的計画法 dp[ i ][ j ] := j番目のindexに位置し、i個の区間を選択済時の最大値 例えば、j番目の…

Problem - C - Codeforces 問題 大きさnの整数配列aが与えられる。 aを3つに分割したとき、分割したセグメントの和が全て等しくなるような 分割方法はいくつあるか。 という問題。 解法 全体の和 を とおく。 前提として、が3の倍数でなければ解は一つも存在…

Problem - B - Codeforces 問題 入力として、が与えられる。 はそれぞれ部屋の縦、横の長さであり、部屋の面積を 以上にしたい。 を満たすように、 の長さを拡張した時の 最小の面積を求めよ。 落とし穴が多く、roomでは解けた人が一人もいなかった。 解法 …

Problem - C - Codeforces 問題 n個の連続した整数があり、m回大きさwの区間の要素を1増やす事ができる。 最も小さい要素を最大化させたい。 解法 二分探索で最も小さい花の高さをmid以上にできるか判定し最大値を探索する。 大きさnの配列を舐めながら、高…

問題 Worst Sportswriter | Aizu Online Judge 解法 aがbに勝ったという情報に対して、順位が a < b となることが保証されている。 入力が順序集合を表すと解釈できるため aがbに勝つならば、 aからbに有向辺を張りグラフを構築し、トポロジカルソートを行え…

問題 Problem - E - Codeforces 解法 与えられる文字列長をnと置く。 2重ループを回し全ての部分文字列を調べれば解が求まるが、nのとる値の範囲が 1<=n<=10^5と大きいため、 では間に合わない。 考察すると、各文字は最終的な解に対し独立してスコアが決ま…