人権なし

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

AtCoder Beginner Contest 133:E - Virus Tree 2

問題

https://atcoder.jp/contests/abc133/tasks/abc133_e

解法

適当な頂点を根とする根付き木を考える.根から DFS をしていく.頂点 v にいるとき,その頂点の子の配色の通り数を考える.子は頂点 v の親と頂点 v の色それぞれと互いに異なる必要があるから,通り数は (K - 2)P(子の数).ただし,v が根であるときは親が存在しなく,v 自身の色も決める必要があるから,通り数は K * (K - 1)P(子の数).あとはこの通り数と各子の頂点の通り数を掛け合わせたものが頂点 v を根とする部分木全体の通り数となる.O(NlogK).

解答

https://atcoder.jp/contests/abc133/submissions/7651473

f:id:babcs2035:20190922125547p:plain

 

AtCoder Beginner Contest 133:D - Rain Flows into Dams

問題

https://atcoder.jp/contests/abc133/tasks/abc133_d

解法

各山に降った雨の総和 S は A_1 + A_2 + ... + A_N であり,山 i と i + 1 に降った雨の総和 x_i + x_(i + 1) は A_i * 2 である.よって,山 1 に降った雨の量 x_1 は S - (A_2 + A_4 + ...) になる.x_k = A_(k - 1) * 2 - x_(k - 1) (k >= 2) の漸化式より,全ての x_i を求めることが出来る.O(N).

解答

https://atcoder.jp/contests/abc133/submissions/7635284

f:id:babcs2035:20190922124005p:plain

 

AtCoder Beginner Contest 133:C - Remainder Minimization 2019

問題

https://atcoder.jp/contests/abc133/tasks/abc133_c

解法

区間 [L, R] に 2019 の倍数が含まれているならば,答えは 0.

そうでない場合,この区間の長さは 2019 未満であるから,i と j を全探索して答えを求めればよい.

解答

https://atcoder.jp/contests/abc133/submissions/7635089

f:id:babcs2035:20190922123358p:plain

 

JOI '20 一次予選1回目:C - マージ (Merge)

問題

https://atcoder.jp/contests/joi2020-yo1a/tasks/joi2020_yo1a_c

解法

動的配列(C++ では std::vector など)を用いる。数列 A, B が空であるかどうかは A.empty() が true であるかどうかで調べることができる。また、配列の末尾に要素を追加するのは C.push_back() を用いればよい。さらに、配列の先頭の要素を削除するのは A.erase(A.begin()) などとすればよい。これらを用いて問題文にあるアルゴリズムを忠実に再現すればよい。計算量は、std::vector.erase() で最悪 O(N) や O(M) かかるので、全体で O(N^2 + M^2)。

C 言語オンリーで解く場合、数列 A, B のどの要素までが削除済みか、あるいは、どの要素が先頭の要素になっているかを要素のインデックスで管理しておくことで、std::vector を用いなくても実装することは容易。こちらのほうが計算量は O(N + M) で済むため効率的。

解答

https://atcoder.jp/contests/joi2020-yo1a/submissions/7627315

f:id:babcs2035:20190921143658p:plain

 

JOI '20 一次予選1回目:B - 母音を数える (Counting Vowels)

問題

https://atcoder.jp/contests/joi2020-yo1a/tasks/joi2020_yo1a_b

解法

文字列 S を先頭から 1 文字ずつ見ていき、'a', 'i', 'u', 'e', 'o' のどれか 1 つに当てはまるとき、答えに 1 加算すればよい。実装は for 文と if 文を用いればよい。計算量は O(N)。

解答

https://atcoder.jp/contests/joi2020-yo1a/submissions/7626873

f:id:babcs2035:20190921142452p:plain

 

JOI '20 一次予選1回目:A - 3 つの整数 (Three Integers)

問題

https://atcoder.jp/contests/joi2020-yo1a/tasks/joi2020_yo1a_a

解法

3 つの整数を受け取り、1, 2 の個数を if 文などを用いて数えればよい。計算量は O(1)。

解答

https://atcoder.jp/contests/joi2020-yo1a/submissions/7626706

f:id:babcs2035:20190921142012p:plain

 

東京工業大学プログラミングコンテスト2019:D - 素数取りゲーム

問題

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_d

解法

各 X_i は何回か (0 回かもしれない) 2 個ずつ取ることができる.X_i を最大何回まで 2 ずつ引いていくことができるかをまず調べる.この回数 + 1 だけ各山に石があると問題を置き換えると,ニムの必勝法を適用できる.O(N + sqrt(10^6)).

解答

https://atcoder.jp/contests/ttpc2019/submissions/7220125

f:id:babcs2035:20190831155117p:plain

 

東京工業大学プログラミングコンテスト2019:C - XOR Filling

問題

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_c

解法

-1 でない a_i の xor を t,-1 である a_i の個数を cnt とすると,0 以上 X 以下の数 cnt 個の xor が X^t となればよい.これは X^t が X * 2 以上であるときは構成できない.そうでないときは,目的の xor が X より大きいときは X,そうでないときはその xor で -1 を置き換えていけばよい.O(N).

解答

https://atcoder.jp/contests/ttpc2019/submissions/7217714

f:id:babcs2035:20190831154408p:plain

 

PCK 2019 予選に出ました

競技開始前

文化祭初日でした.極めて忙しかったので,全く競プロをやっていませんでした.直前にセグ木を数本書いて競プロとは何か思い出そうとしていました.

競技開始直前

学校で用意された WiFi に接続できない(悲しい).

結局がんばると繋がりました(非自明).

問題1~3

相方に投げた.令和で通してくれたので感謝です.

問題1を 01:23,2を 05:34,3を 07:19 で AC.

問題4

最初「かかる時間の総和」だと思っていたが「かかる時間の Max」を求める問題だと気付いた.誤読のせいで時間ロス.13:09 で AC.

問題5

キューを素直に実装.慎重に実装したので令和だった(よかった).19:26 で AC.

問題6

フィボナッチだけど何も分からん.パス.

問題7

なにこれ自明っぽいじゃ~ん,となるがよく考えると非自明.

しかし,よく考えると O(2^N * N) が通るので Bit 全探索を書くと通りました.60:07 で AC.

問題8

「JOI 国のお散歩事情」に問題背景が似ている.

矢印は貪欲に前に動かすのみでいいよね!と決めつけて実装して WA.

よく考えると,いくつかを左まで可能な限り移動し,残りを右まで可能な限り移動するのが最適っぽいとなる.実装するが WA.

コードをにらむと for の探索範囲が 1 だけ間違えていることが発覚.修正して 120:04 でAC.

また問題6

愚直に四角形を追加していく過程をシミュレーションする解法が降ってくる.計算量的には全く問題ないが実装がつらい気持ちになった.何とか令和で AC.167:45.

競技終了後

顧問に8完2WA というだいぶ微妙な結果を伝えて文化祭の展示に戻る.そのまま文化祭打ち上げ Part 1 に行った.

本選に

行きたい

 

JOI Kakisemi Contest 2019:E - 偏りの無いビル

問題

https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2156

解法

小課題1

|H_1 - H_2| >= 2 を判定すればよい.

小課題3

N <= 2000, A_i <= 30 より全探索で解ける.O(N^2).

 

あとの小課題は A_i <= 10^9 となるので座標圧縮をしたい.ここで,差が 1 のところはそのまま,2 以上のところは差が 2 になるように座標圧縮をする.これで O(N^2) まで計算量を落とすことができる.

 

小課題5

A_i <= A_(i + 1) より A は単調増加.差が 2 以上であるところで区切ると,この区切った境界を挟んだ部分列は答えに含まれない.よって,境界間で答えを数える.各境界間の区間の長さを l とすると,C(l, 2) + l がその区間での答えになる部分列の個数となる.この和を求めればよい.

小課題6

{ A } = (2, 4, 3, 6, 6, 3, 5, 2) を考える.max = 6, min = 2, 種類数 cnt = 5 であるから,答えは (max - min) - cnt = -1 .これが答えとなる必要十分条件になる.

部分列の左端 L を固定して考える.部分列の右端 R を右に動かしていったとき,max, min, 種類数 が更新されるのは新しい数が出現するときのみ.なので,新しい数がどの位置で出現するのかを求めればよい.O(N * 30 * logN).

小課題7~9

(max - min - cnt) を記録していくことを考える.ある数が出現したとき,その数が出現した位置よりも後の区間の (max - min - cnt) の値が全て +1 される.これを Range-Add のセグ木におく.ここで,区間更新した区間の数だけこれより先に加算しなければいけなくなる区間の数は減る.なので,区間更新の回数は 2 * N に抑えられる.遅延セグ木を使うと O(NlogN) になる.これを定数倍高速化すると満点が得られる.