人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Codeforces Round #530 (Div. 1):A. Sum in the tree

問題

codeforces.com

解法

b_i を「頂点 i を根とする全て部分木に含まれる s の最小値」とおく.このとき,b_i < s_i であるような頂点が存在したらその木は構成不可能なので -1 を出力すればよい.

木が構成出来る場合,木全体を根から(すなわち頂点 1 から)見ていく.「dfs(i, s) := 今頂点 i を見ていて,パスにある頂点の a の和が sum のとき」と DFS を立てて,a_i = b_i - sum とすればよい.これを全ての頂点について処理し a を求めればよい.O(N).

解答

codeforces.com

f:id:babcs2035:20190319065853p:plain

 

Codeforces Round #534 (Div. 1):A. Grid game

問題

codeforces.com

解法

縦長のタイルは 4x4 のマスの上半分,横長のタイルは下半分にひたすら敷き詰めていけば永遠に敷き詰められる.なぜなら,上半分に関しては 4 つ設置すると上から 1, 2 行目が消えて,下半分に関しては 2 つ横に並べて設置するとその行が消えるから.O(|S|).

解答

codeforces.com

f:id:babcs2035:20190319064516p:plain

 

yukicoder:No.800 四平方定理

問題

yukicoder.me

解法

2つ目の条件式の左辺に x, y, z の 3 文字,右辺に w の 1 文字となっていて全探索するには O(N^3) かかってしまい間に合わない.そこで,この式を変形して,x^2 + y^2 = -z^2 + w^2 + D とすることで左辺・右辺の取りうる値ごとに (x, y), (z, w) の組がいくつあるかを全通り試すことが出来る.

実装では,配列を用いず std::map や std::set を用いると全体の計算量に O(logN^2) がつくことになり最悪 TLE になってしまう.両辺共に取りうる値の範囲が決まっているので std::vector などで数えればよい.O(N^2 + N^2).

解答

yukicoder.me

f:id:babcs2035:20190319062814p:plain

 

AtCoder Grand Contest 031:C - Differ by 1 Bit

問題

atcoder.jp

解法

1回の操作でどこか1つの bit を反転させるので,A と B の立っている bit 数の偶奇は必ず違う.なので,偶奇が同じ場合は必ず操作を構成できないので NO.逆に偶奇が異なる場合は必ず構成できる.

再帰的に構成を求めていく.まず,A と B で異なる bit が必ずある(A != B なので).その bit の桁を k とすると,A, B の k-bit 目を削除した (N - 1) bit の数をそれぞれ C, D とおくと,C, D の立っている bit 数の偶奇は,前の動作で異なる bit を削除したので,必ず等しい.ここで,C, D と立っている bit 数の偶奇が異なる数 E (C <= E <= D) をおく.これは C のどこか(どこでもいい)の bit を反転させることで作れる.すると,C ~ E で操作を構成することができ,また,E ~ D でもできる.これら2つの順列の k-bit 目に A, B の k-bit 目をそれぞれ追加すれば A ~ B の操作を構成することができる.実装では,C ~ E, E ~ D それぞれの両端を A, B として上の処理をしていく.区間の長さが 2^1 になったときの操作は自明に (A, B) になる.O(N^2 * 2^N).

解答

atcoder.jp

解説を読んでも理解できず,解くまでかなり時間がかかった.解法さえわかれば実装はそんなに重くないと思った.

f:id:babcs2035:20190317161054p:plain

 

AtCoder Grand Contest 031:B - Reversi

問題

atcoder.jp

解法

dp(i) := i 個目の石までの塗り方の数

とする.このとき,i 個目の石と同じ色の石が j (j < i) 個目にあるとき,[j, i] の区間を i 個目の石の色で塗ることが可能.塗るときの塗り方の数は考えられる j について dp(j - 1) を足したものになる.よって,dp(i) は dp(i - 1) と dp(j - 1) (j < i で C_i = C_j を満たす全ての j) の和になる.このままだと O(N^2) かかってしまうが,後者の和を C_i ごとにメモしておくことで O(1) で遷移できるようになる.これで全体で O(N) になり解ける.

解答

atcoder.jp

コンテスト中は全体を見て答えを一発で求めようとしてしまっていた.こういう問題で DP は生きてくると思った.

f:id:babcs2035:20190317131138p:plain

 

AtCoder Grand Contest 028:B - Removing Blocks

問題

atcoder.jp

解法

各ブロックについてそのブロックの重さが答えに加算される回数を求めたい.ブロック i の重さが加算される回数を求める.ブロック i とブロック j が連結である場合の数を P(i, j) とおく.P(i, j) (1 <= j <= N) の和がブロック i の重さが答えに加算される回数になる.

i <= j の下で考えると,ブロック i とブロック j が連結であるとき,区間 [j, i] のブロック (|i - j| + 1) 個は,どれも取り除かれていない.一方,それ以外の区間のブロック N - (|i - j| + 1) 個は,取り除かれていても取り除かれていなくてもどちらでもいい.ブロックを取り除く順番を {1, 2, 3, ..., N} の順列であらわすことにすると,区間 [j, i] のブロックの取り出し方は (j, {j + 1, j + 2, ... , i}) となり,この場合の数は (|i - j|)! となる.この取り出し方を長さ N の順列に当てはめるので,この場合の数は C(N, |i - j| + 1) となる.区間 [j, i] 以外のブロックの取り出し方の場合の数は (N - (|i - j| + 1))! となる.よって,P(i, j) は,式を整理して,

P(i, j) = (|i - j|)! * C(N, |i - j| + 1) * (N - (|i - j| + 1))! = N! / (|i - j| + 1)

となる.よって,j の位置は関係なく,区間 [j, i] の長さ (|i - j| + 1) が P(i, j) に関係すると分かる.

ここで,i によって (|i - j| + 1) が取る値の個数が変わってくる.具体的には,N = 6 のとき,(|i - j| + 1) の値は 1, 2, 3, 4, 5, 6 のどれかを取るが,j が変化することによってそれぞれの値が現れる回数を (a, b, c, d, e, f) 回とあらわすことにすると,

i = 1 のとき (1, 1, 1, 1, 1, 1) 回

i = 2 のとき (1, 2, 1, 1, 1, 0) 回 

i = 3 のとき (1, 2, 2, 1, 0, 0) 回

i = 4 のとき (1, 2, 2, 1, 0, 0) 回

i = 5 のとき (1, 2, 1, 1, 1, 0) 回

i = 6 のとき (1, 1, 1, 1, 1, 1) 回

というように変化する.よく眺めるとこれには規則性があって,i が (i - 1) から変化するとき,i の値を取る回数が + 1 され,(N - (i - 1) + 1) の値を取る回数が - 1 される.

各ブロック i が答えに加算される回数は P(i, j) * ((|i - j| + 1) の値を取る回数) (1 <= j <= N) となり,答えは 1 <= i <= N について上の式を計算し,全て足したものになる.(|i - j| + 1) の値 を取る回数は前に示した規則性より前計算 O(N) と遷移 O(1) で求められるので,全体で O(N).mod の割り算があるので逆元を用いる.

解答

atcoder.jp

解説を読んでやっと理解できた.答えに要素がかかわる回数を求める系の問題だった.

f:id:babcs2035:20190316162432p:plain

 

yukicoder:No.798 コレクション

問題

yukicoder.me

解法

全ての商品をお金を出して買うとすると,答えは

(A_1 + A_2 + ... + A_N) + (B_1 * 0 + B_2 * 1 + B_3 * 2 + ... + B_N * (N - 1))

となる.この式から,B が小さい順に早く購入した方がよいことが分かる.なので,B が小さい順に商品を見ていき,各商品について買うかどうかを DP で最適な解を見つける.

dp(i, j) := (i - 1) 番目の商品までを j 日で手に入れたときの最小の金額

と DP を定義する.遷移は O(1) なので全体で O(N^2).

解答

yukicoder.me

本番中,貪欲がダメであることは分かって DP だろうと予想は立てられたが,具体的には思いつかなかったので反省.

f:id:babcs2035:20190316123527p:plain

 

JOI '08 春合宿1:3- Flu インフルエンザ

問題

https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf

解法

k 日目までに感染の広がる様子をシミュレーションする.流行している都市から感染が拡大する範囲が d <= 25 と狭いので,現在流行している都市それぞれを中心とする一辺が 2 * d の正方形内にある都市を探す.ある座標に都市があるかどうかは逆配列等を用いて O(1) で求めることが出来る.正方形内にある都市のうち,正方形の中心の都市から距離が d 以内であり,まだ感染していないものに感染が拡大する.次の日はこれらの都市について同様に処理すればよい.それぞれの日で新たに流行した都市は問題文の制約より高々 10 しかないので,このシミュレーションは十分間に合う.これによって各都市について感染する日が分かったので,k 日目に各都市で流行しているかどうかが分かる.O(k * d^2 + n).

解答

atcoder.jp

f:id:babcs2035:20190315164046p:plain

 

JOI '09 予選:5- シャッフル

問題

www.ioi-jp.org

解法

カードの枚数に対してシャッフルの回数がとても少ないので,ほとんどバラバラにならない.なので,連続する数字が書かれるカードを1つの区間としてもっておき,その区間をシャッフルによって切ったり,並び替えたりすることにする.

例えば,n = 10 として,初めにシャッフル (3, 5) をするとき,3つの区間 {[1, 3]}, {[4, 5]}, {[5, 10]} が出来,カード全体は {[5, 10]}, {[4, 5]}, {[1, 3]} となる.その後シャッフル (2, 7) をすると,5つの区間 {[5, 6]}, {[7, 10], [4, 4]}, {[5, 5], [1, 3]} が出来,カード全体は {[5, 5], [1, 3]}, {[7, 10], [4, 4]}, {[5, 6]} となる.これを全てのシャッフルについて同様に処理すればよい.O(m^2).

解答

atcoder.jp

一発 AC 出来たのでよかった.

f:id:babcs2035:20190315143815p:plain

 

JOI '09 本選:3- あみだくじ

問題

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf

解法

ある横の辺を消すということは,その辺を通る2つのパスの中のその辺の高さ以降のパスが逆になることを意味する.ゆえに,任意の横の辺を消したとき,ある2つの縦棒のスコアが逆になる.この「ある2つの縦棒」を全ての横の辺について調べることを考える.これは全ての縦の辺について愚直にシミュレーションし,その過程で通った横の辺にメモをしていく形で求めることが出来る.

全ての辺についてその辺を消したときに J 君の得点がどう変化するかを,得点の変化する差分を計算し求めればよい.O(NH + M).

解答

atcoder.jp

0-index と 1-index が混在していて実装ミスをしていた.

f:id:babcs2035:20190314152128p:plain