水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

PCK 2016 本選:5 - 環状すごろく

問題

Aizu Online Judge

解法

あるマスから飛ぶ先のマスに辺を張り,各マスから同じマスを2度まで通る DFS をする.一回一回の DFS ごとに,1回しか通らなかったマスを答えから除外していく.これを全てのマスについて計算すればよい.O(N).

解答

Aizu Online Judge

計算量の見積もりを間違えてしまい 1 WA してしまった.

f:id:babcs2035:20181116220500p:plain

PCK 2016 本選:3 - 有理式最大化

問題

Aizu Online Judge

解法

割られる数を出来るだけ大きく,割る数を出来るだけ小さくすることを考えればよい.割る数 C - D の C, D を全通り試し,余ったもののうち大きいもの2つを A, B に充てればよい.O(N^2).

解答

Aizu Online Judge

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

f:id:babcs2035:20181116215744p:plain

PCK 2017 本選:5 - 朝昼晩ごはん

問題

Aizu Online Judge

解法

朝・昼・晩の時間の決め方は,単純に考えると (24*60)^3 通り.これを全て計算していては間に合わない.時間の決め方は N 人の3つの時間の区間の始点と終点の数だけに抑えることが出来るので N^3 通りになる.それぞれについて,その時間に何人が当てはまるかを計算すればよい.O(N^4).

解答

Aizu Online Judge

1回 TLE を出してしまった.

f:id:babcs2035:20181113200015p:plain

PCK 2017 本選:4 - 電子メトロノーム

問題

Aizu Online Judge

解法

t_i それぞれを t_i の最大値(M とおく)の約数にすることを考える.M の約数は O(MlogM) で列挙出来るので,各 t_i について t_i 以上で最も小さい約数にすることを考えればよい.O(MlogM).

解答

Aizu Online Judge

一発 AC だったのでよかった.

f:id:babcs2035:20181113195320p:plain

HACK TO THE FUTURE 2019 予選

結果

82829 点,440:23,519 位中 272 位.終わりの一時間だけの参加になった.

f:id:babcs2035:20181110221922p:plain

f:id:babcs2035:20181110221931p:plain

A - ばらばらロボット

何も考えずに外周を R で囲っただけ.

https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3579513

f:id:babcs2035:20181110222423p:plain

JOI '15 春合宿 4:1 - 遺産相続

問題

https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d4.pdf

解法

K 人それぞれに Union Find 木を構成し,辺のコストが高い順に辺を見ていく.辺ごとにどの人に辺を割り振るかを考える.この時,ある人を境に辺を含めることが可能になるので,その人を二分探索で探す.辺を含めることが可能になるかどうかの判定はそれぞれの人の Union Find 木で辺の両端が追加されているかどうかで出来る.O(MlogM).

解答

beta.atcoder.jp

二分探索の判定部で,どの人も辺を含めることが出来ない場合の処理を書いていなく,WA を連発してしまった.二分探索を単体で使うだけではない解法で使う方法を知った.

f:id:babcs2035:20181110134840p:plain

JOI '15 春合宿 2:1 - ビルの飾りつけ 3

問題

https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d2.pdf

解法

元の数列である A を構成する条件は,

1 <= A_i <= max(A_0, A_1, A_2, ... , A_(i - 1) ) + 1

であるので,B_i も同様に

1 <= B_i <= max(B_0, B_1, B_2, ... , B_(i - 1) ) + 1

となる.まず,全ての B の要素が上の条件を満たすか調べる.もし,条件を満たしていない箇所がある場合,B のその箇所より前に要素を追加することで条件を満たすようにできるかどうか判定する.具体的には,

  • max(B_0, B_1, B_2, ... , B_(k - 1) ) と B_k の差が 2 以上ある箇所が1つでもある場合
  • 1 <= B_i <= max(B_0, B_1, B_2, ... , B_(i - 1) ) + 1 を満たさない箇所が複数ある場合

に答えが 0 になる.max(B_0, B_1, B_2, ... , B_(k - 1) ) と B_k の差が 2 以上ある箇所が1つの時は,その箇所の前までで (B_k) - 1 を追加できる箇所の数が答えになる.B だけで条件を満たしている場合は,全ての箇所について追加できる数の通り数を足し合わせればよい.この時,B_(i - 1) と B_i,B_i と B_(i + 1) の間に同じ要素を入れると作られる A はどちらも同じものになってしまい重複が発生するので,答えから N - 1 を引く.O(N).

解答

beta.atcoder.jp

「max(B_0, B_1, B_2, ... , B_(k - 1) ) と B_k の差が 2 以上ある箇所が1つの時は,その箇所の前までで (B_k) - 1 を追加できる箇所の数が答えになる」ということに気付かず 9 WA した.

f:id:babcs2035:20181109225511p:plain

AtCoder Beginner Contest 113

結果

3完(600 点,15:45),2359 位中 328 位.B 問題で痛恨の実装ミスをしてしまい 1 WA を出してしまったのが順位に響いてしまった.また,D 問題を解くことが出来なかったのがつらかった.もし Rated だとしたらレートは間違えなく下がっていたと思うので,気を付けたい.

f:id:babcs2035:20181105205448p:plain

f:id:babcs2035:20181105205535p:plain

A - Discount Fare

beta.atcoder.jp

B - Palace

小数の扱いミスで 1 WA してしまった.

beta.atcoder.jp

C - ID

babcs2035.hateblo.jp

D - Number of Amidakuji

babcs2035.hateblo.jp

AtCoder Beginner Contest 113:D - Number of Amidakuji

問題

beta.atcoder.jp

解法

ぱっと見 DP をしたい気持ちになるので,以下のように DP を定義する:

dp(h, w) := スタートから h 行 w 列に行くまでのあみだくじの通り数の合計

後は,DP の遷移を考える.この時,今いる行の次(すなわち h + 1 行目)のどこに行くかで場合分けする.これは,左に移るか,右に移るか,このまま下に行くかの3通りある.3通りそれぞれの場合になる h 行目の横線の入れ方を bit 全探索する.横線が隣り合ってはいけないという制約に注意して実装すると,求める dp(h, w) は以下のように求められる:

dp(h, w) = dp(h + 1, w - 1) * (左に移れる横線の入れ方の通り数) + dp(h + 1, w) * (このまま下に行ける横線の入れ方の通り数) + dp(h + 1, w + 1) * (右に移れる横線の入れ方の通り数)

O(HW * (2^W)).

解答

beta.atcoder.jp

コンテスト中に解けなかった.シンプルではあるが,DP 上で bit 全探索をするのは斬新だった.

f:id:babcs2035:20181105204918p:plain