AtCoder 400 点問題
問題 解法 解答 問題 beta.atcoder.jp 解法 奇数個のコインがあるマスから (1, 1) -> ... -> (1, W) -> (2, W) -> ... -> (2, 1) -> ... のように他の奇数個のコインがあるマスにコインを移していく．これをやると，最小でも HW - 1 個は偶数個にすることが…
問題 解法 解答 問題 D - Factorization 解法 M を素因数分解する．M の各素因数を N 個の箱に分けていくと考えればよい．このとき，単純に N ^ (各素因数の個数) を掛け合わせたものを答えにしてしまうと，重複が生まれてしまう．なので，重複組み合わせ H(…
問題 解法 解答 問題 D - Candy Distribution N 個の箱があり，それぞれ A_i (1 <= i <= N) 個キャンディーが入っている．ここで，任意の個数の連続する箱を選び，それらの箱に入っているキャンディーの合計が M で割り切れるようにしたい．連続する箱の選び…
問題 解法 解答 問題 D - AtCoder Express 2 東西に伸びる線路に都市が N 個あり，M 本の列車が都市 L_i と R_i の間を走っている．以下のクエリが Q 個与えられるので，それらに答える問題：都市 p_i と q_i の区間に走る区間が完全に含まれる列車の数． N …
問題 解法 解答 問題 C - 右折 N 行 M 列のマス目が，障害物と通路の２つの要素で構成されている．ロボットは通路マスのどれかから４方のどれかの方向に向かって１マス以上進む．その後，右に方向を変え，１マス以上進む．このとき，ロボットの進み方の通り…
問題 解法 解答 問題 D - We Love ABC A,B,C,? で構成される文字列 S が与えられる．? は A,B,C のどれにも変化できる．このとき，S の中から３つ文字を選び，この選んだ文字を並べると ABC になる選び方の通り数を求める問題．|S| <= 10^5． 解法 SugarDrag…
問題 解法 解答 問題 B - 交通費 x 軸上に N 人の人がいる。ある x 軸上の点 c をおき、そこから d 以内の人には abs(x - c) だけ交通費が支払われ、c から d より遠い人は一律で d 払われる（つまり、min(abs(x - c), d)）。これを Q 回行うとき、それぞれ…
問題 D - Score Attack 重み付き有向グラフが与えられ、頂点1 ~ N に移動する時の最大コストを求め、かつ、そのパス中に閉路があり無限にコストを高められる場合はそれを検出しなければならない。 解法 Bellman–Ford 法以外に何かあるのか？ 解答 Submission…
問題 D - Maximum Average Sets N 個のそれぞれ価値が決まった品物があり、そこから A 以上 B 以下個選ぶ。ここで、選んだ品物の価値の平均の最大値を求め、また、その最大値になるような品物の選び方の通り数を求める。 解法 品物を価値でソートし、とりあ…
問題 D - Mixing Experiment ２つのタイプの成分が (a_i,b_i) だけ含まれ、値段が c_i の薬品が N 個あるとき、２つのタイプの成分の比を Ma : Mb にするときの値段の最小値を求める問題。 解法 「dp(i, j, k) := i 番目の薬品まで見たとき、２つの成分を (j…
問題 D - Candidates of No Shortest Paths 無向連結グラフが与えられ、全頂点間の最短パスに使われていない辺の数を求める問題。 解法 頂点の数が <= 100 なので、ワーシャルフロイド法で全頂点間の最短距離を求める。その後、各辺について、全頂点から両端…
問題 D - Patisserie ABC N 個の「綺麗さ」「おいしさ」「人気度」の３つの要素があるケーキを M 個選んで食べる（重複なしで）。この時、綺麗さの合計の絶対値 + おいしさの合計の絶対値 + 人気度の合計の絶対値の最大値を求める問題。３つの要素の値は負数…
問題 D - Equals 1~N の順列 p の中で (x,y) 番目のものを swap 出来るとき、最大でいくつの数をもとの位置に戻せるか、という問題。 解法 順列内の数を頂点、swap 出来る関係を辺として図を書いてみると、連結な部分は連結の範囲の中の任意の場所に移動可能…
問題文 C - XORパズル / Solving XOR-Puzzles beta 版だと表示が崩れている。 数列 a の中から任意の個数を取り出して、それらの XOR が K になる数列の個数を求めよ、という問題。bit 系の問題は発狂。 解法 「dp(i, j, k) := 数列 a の i - 1 個目までで j…
