人権なし

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

JOI 2019/2020 本選 参加記

(ブログ記事書くのが久しぶりすぎてはてブロの UI に困惑している)

Day -1

学校で「プロシードテスト」というものを受けさせられた.主催者は今話題の Benesse

Day 0

UbuntuEclipse に慣れようと思い,本選環境の整備を始める(本選対策の始まり).VM のダウンロードリンクが載ったメールを紛失してしまうが,mencotton 氏に教えていただいた(ありがとうございました).

Eclipse-CDT が入っていないじゃないかと困惑するが,仮想環境内でログインする先のアカウントを間違えていたと判明.

結構手こずってしまい,対策が出来ず.本当に本選er としてやる気あるのか???

Day 1

朝,ツイートしようとしたら Twitter で障害が発生していて発狂した.

午前中は学校で授業.

学校終了後,北千住でたっちゃん氏・悪商人氏・SugarDragon5 氏とガスト北千住店で集合.義務であるカルボナーラをいつも食べていたので,違うパスタを食べた.この義務を守らない行いが後々結果に響いてきたのかもしれない.

その後つくば新幹線 (TX) に乗って,蟻本を n 年ぶりに読む.がしかし,寝てしまい,終点・つくば駅でたんちゃん氏に起こされた・・・(そのまま寝ていたら秋葉原送りでした,ありがとうございました).

途中,つくばカピオを眺める.

ラクティスまでの時間,蟻本に飽きたのか,なぜか Bot をいじくってしまう.

ラクティスでは,環境整備に時間がかかったが,スムーズに全完.蟻本をここでしっかり読もうと決めていたのでしっかり読んだつもりになるまで読んだ.

その後,講演が行われた.テーマは OSS = オープンソースソフトウェア.GitHubリポジトリに Star が付くと喜ぶのは凄く共感できた(そこ?!).

その後は夕食.なんか去年と一緒だった(文句では全くありません).

予選全完賞対象者が多すぎてヤバかった.

そして,ついに「入所」.

ロビーで Bot を少しいじくり,蟻本を写経したりして 0:35 に就寝.布団が 2 セットあってガチ困惑した.

Day 2

起床は自明に AC.

朝食は「いつもの」超質素.

その後,無事出所.

バス出発までの時間はロビーで,その後はバス内で各種基本セグ木と Dijkstra 法を空で書けるかチェックした.

つくば国際会議場に到着し,いよいよ本選本番.

まず,環境整備に 10 min ぐらいかかった(???).

A 問題を眺める.見た瞬間に解法が分からなかったので「去年の A 問題より難しくないか?」と思った.まあ普通にやって通る.ここまで 20 min ぐらい.

B 問題を眺める.最終的に残す文字列の左端を固定すれば,必要なコストは一意に定まるとすぐに気づけてよかった.A 問題より自明では?となり,実装して通る.ここまで 40 min ぐらい.

C 問題を眺める.Static Sushi みたい.よくわからないけれど「折り返しは 1 回だけでいいのでは」となって嘘 DP を書いて WA を連発.その後,複数回の折り返しを考慮した DP を書いて 25 点を取る.ここまでで 1:30 ぐらい.

D 問題を眺める.グラフ問だけど,何も分からん.自明部分点 5 点だけ取って逃げる.

E 問題を眺める.クエリ系問だけど,何も分からん.とりあえず,セグ木で殴れるものだけ殴って 14 点は確保.

その後 C 問題を完答しようと考察をするが時間切れ.結果,100 + 100 + 25 + 5 + 14 = 244 点で終了.

mencotton 氏と全く同じ点数の取り方をしていて驚いた.

A, B を早く通せたのに C を完答できなかったのは普通に悔しかった.

解説を聞いたが,やはり難しい.時間内に実装を間に合わせるだけでやっとだと思った.

帰りは LCA の駅まで[自己規制(個人情報につながりうるので)]氏と帰った.

まあほぼ引退を確信.

Day 3

学校の 1 時間目の授業が終わって JOI のホームページを確認していたらボーダー 301 点と公表されていた.やはり落ちた.

これからはちょっと Bot の整備を終えてから,大学受験をまじめにやります.大学でまた競プロをリハビリから始めたい.

 

AtCoder Beginner Contest 151:F - Enclose All

問題

https://atcoder.jp/contests/abc151/tasks/abc151_f

解法

求める半径を二分探索で求める.

半径を r に決めたとき,任意の 2 点を円の中心,半径を r とした円の交点は 2 つに定まる.そして,この 2 点それぞれを円の中心,半径を r とした円 2 つが N 個全ての点を内部または周上に含むかどうかを判定すればよい.このような円が 1 つでもあれば半径 r は十分な大きさだと分かる.1 つもなければ r よりも大きい半径を考える必要があると分かる.O(N^3 * log(ans)).

解答

https://atcoder.jp/contests/abc151/submissions/9471462

f:id:babcs2035:20200112223421p:plain

 

AtCoder Beginner Contest 148:D - Brick Break

問題

https://atcoder.jp/contests/abc148/tasks/abc148_d

解法

壊すレンガの数を少なくするには残すレンガの数を増やせばよいので,できる限り 1, 2, 3, ... の列を長くすればよい.これは,次に残したい数字 k(最初は 1)を保持しながら左端からレンガを見ていき,k 以外の数字のレンガが現れたらひたすら壊し,k の数字のレンガが現れたら k++ する,という風に処理すればよい.O(N).

解答

https://atcoder.jp/contests/abc148/submissions/9061407

f:id:babcs2035:20191222222633p:plain

 

AtCoder Beginner Contest 148:E - Double Factorial

問題

https://atcoder.jp/contests/abc148/tasks/abc148_e

解法

N が奇数のとき,答えは 0.なぜならば,f(N) は素因数に 2 と 5 を持たないから.

N が偶数のとき,f(N) が 5 で割れる回数が答えとなる(正確には 2 で割れる回数との min になるが,5 で割れる回数の方が圧倒的に小さいため).これは,N / (2 * (5^k)) (1 <= k) の和になる(イメージ的には 2 ~ N の偶数のうち 5 で割れるもの, 25 で割れるもの,... の個数を計算していく感じ).O(log_5(N)).

解答

https://atcoder.jp/contests/abc148/submissions/9072149

f:id:babcs2035:20191222223338p:plain

 

AtCoder Beginner Contest 148:F - Playing Tag on Tree

問題

https://atcoder.jp/contests/abc148/tasks/abc148_f

解法

高橋君は木のどこかの葉に逃げるのが適切なので,それぞれの葉に逃げたときの青木君の移動回数を求め,それらの max を答えとすればよい.

まず,ある葉(頂点 t)までの距離 dist_ut と dist_vt が dist_ut >= dist_vt のとき,高橋君は葉 t に到達する前に青木君につかまってしまう.このときの青木君の移動回数は dist_uv / 2 回.

一方,dist_ut < dist_vt のとき,高橋君は葉 t に到達することが出来る.その後は葉 t の一歩手前の頂点 t' と t をうろつくのが良い.ここで dist_uv がいかなる場合も高橋君は頂点 t' でつかまることが分かる.よって,青木君の移動回数は dist_vt - 1.

頂点間の距離の取得は LCA 木を前計算で準備しておくと O(logN) で可能.全体で O(NlogN).

解答

https://atcoder.jp/contests/abc148/submissions/9080471

f:id:babcs2035:20191222224006p:plain

 

AtCoder Beginner Contest 144:F - Fork in the Road

問題

https://atcoder.jp/contests/abc144/tasks/abc144_f

解法

M 本の辺それぞれをふさいだときの E を計算していては O(M^2) となり間に合わない.ここで,ある頂点 v から出る辺のうち 1 つを塞ぐとするとき,v とつながる先の頂点から頂点 N までの経路数が最も多いような辺を塞ぐのが最適.各頂点から頂点 N までの経路数は簡単な DP で求めることが出来るから,この DP を全ての v (1 <= v <= N) について実行し,E の最小値を答えにすればよい.各 DP が O(N + M) であるから,全体で O(N(N + M)).

解答

https://atcoder.jp/contests/abc144/submissions/9036671

f:id:babcs2035:20191221151707p:plain

 

AtCoder Beginner Contest 144:E - Gluttony

問題

https://atcoder.jp/contests/abc144/tasks/abc144_e

解法

「チーム全体の成績を k 以下にすることが出来るか」を基準とする二分探索で答えを求める.これは A を昇順,F を降順にソートしておき,この順番で担当する食べ物を割り当て,それぞれが k 秒以内に食べ終えるための修行回数を計算し,この和が K 以下であるかどうかを計算すればよい.O(Nlog(答え)).

解答

https://atcoder.jp/contests/abc144/submissions/9030374

f:id:babcs2035:20191221150911p:plain

 

AtCoder Beginner Contest 144:D - Water Bottle

問題

https://atcoder.jp/contests/abc144/tasks/abc144_d

解法

底面の辺を軸として傾けているから,平面で考えてよい.ある角度より傾けると水がこぼれるという単調性があるから,「角度 θ 傾けたとき,水がこぼれるかどうか」を基準とした二分探索を行えばよい.

θ だけ傾けたときに容器内に含むことが出来る水の量は,平面上で三角形上になるか台形状になるかの 2 通りに場合分けし,tanθ を用いて計算できる.

解答

https://atcoder.jp/contests/abc144/submissions/9029976

f:id:babcs2035:20191221150259p:plain

 

AtCoder Beginner Contest 145:F - Laminate

問題

https://atcoder.jp/contests/abc145/tasks/abc145_f

解法

まず,数列 H を扱いやすいように座標圧縮しておく(最小を 1 としなければいけないことに注意).そうすることで H の要素は高々 N + 1 以下になる.また,H[k] < H[k + 1] となるときのみ,新たに H[k + 1] - H[k] 回の操作が必要となる(反対に,高さが同じか低くなるときには,新たに操作は必要にならない).これを踏まえ,以下の DP を考える.

dp(i, j, k) := i - 1 列目までのいくつかで操作を行い,あと j 回操作が可能で,i - 1 列目の H が k であるときの,これから行わなければならない操作の回数の最小値

遷移は H[k] を k に変更するか,そのまま変更しないかの 2 通りであるから,

dp(i, j, k) = min(dp(i + 1, j, H[i]) + max(H[i] - k, 0), dp(i + 1, j - 1, k))

となる.max(H[i] - k, 0) は H[i] <= k のときは操作回数は増えないことを意味している.この部分で座標圧縮した分の差を復元する必要がある(操作回数が小さくなってしまうので).O(N^2 * K).

解答

https://atcoder.jp/contests/abc145/submissions/9001512

f:id:babcs2035:20191218153939p:plain

 

AtCoder Beginner Contest 145:E - All-you-can-eat

問題

https://atcoder.jp/contests/abc145/tasks/abc145_e

解法

まず,食べることにした料理の中では食べるのに必要な時間が短い順に注文するのが最適なので,料理を食べるのに必要な時間が短い順にソートしておく.ここで以下の DP を考える.

dp(i, j) := 時刻が j のとき,i 番目の料理以降で得られるおいしさの和の最大値

遷移は i 番目の料理を食べるか,食べないかの 2 通りであるから,

dp(i, j) = max(dp(i + 1, j + A_i) + B_i, dp(i + 1, j))

となる.O(NT).

解答

https://atcoder.jp/contests/abc145/submissions/9001181

f:id:babcs2035:20191218152339p:plain