bouzuya.hatenablog.com

ぼうずやのにっき

第八回 アルゴリズム実技検定 (PAST) L - K番目の絶対値 を解いた

第八回 アルゴリズム実技検定 (PAST) L - K番目の絶対値 を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_l

「連続した空でない部分列の総和」は累積和の 2 点の差で求める。 2 点の全探索は O(N^2) で N <= 3*10^5 からこれは間に合わない。すべてのスコアを求めて K 番目を求めることはできない。

こういう場合はスコアを二分探索してみる。スコア x を決め打ちしたときに x よりも小さいスコアの個数が K 個未満と以上で二分探索すれば K 個以上の側が答えになる。

……ここまで考察したのだけど K 個以上の位置を計算量を下げつつ探索する方法が分からなかった。

解説: https://atcoder.jp/contests/past202109-open/editorial/2398

考察した範囲では正しかった。 |S_j - S_i| <= x (i < j && i != j) な 2 点を探索すれば良く、もう順序は問題にならないのでソートしてしまって良い。これに気づかなかった。ソートしてしまえば単に s[i+1..].upper_bound(&(s_i + x)) の和で個数が求められる。

解説では尺取法を使っているが各値に対して upper_bound の二分探索でも各探索が O(N) から O(NlogN) になる程度なので間に合う。

これはがんばれば解けたかもしれない……。ちなみに INF の誤りと探索する値の誤りなどで 2 WA している。

提出: https://atcoder.jp/contests/past202109-open/submissions/28796885

今日のコミット。

AtCoder Beginner Contest 236 (ABC236) D - Dance を解いた

AtCoder Beginner Contest 236 (ABC236) D - Dance を解いた。

問題: https://atcoder.jp/contests/abc236/tasks/abc236_d

本番では解けなかった。そのときに考えたこととしては……。 XOR の処理から途中で最善のものを判断することは難しそうなのでおそらく全探索だろうと判断した。愚直にやってしまうと 16! で間に合わない。 2 グループに分ける 16 C 8 ごとに 8! で考えたのだけど 108 で間に合わなかった。

解説を見ると、 DFS で全探索し各ペアの小さい側を未選択のもののうち最小にするようにしていた。これで 15 * 13 * 11 * 9 * 7 * 5 * 3 * 1 通りで 106 で間に合うらしい。

今日のコミット。

2022-W03 ふりかえり

2022-W03 をふりかえる。

2022-W03 の目標 とその記事

目標。

記事。

つくったもの

よんだもの

(なし)

みたもの

(なし)

その他

勉強会。

(なし)

おでかけ。

(なし)

ゲーム。

買い物。

(なし)

体調。

育児。

  • 上の子はトイレの失敗がほとんどなくなった
  • 下の子は下痢が一週間以上も続いている

2022-W03 はどうだったか。

体調不良もあって良くなかった。

ABC236 は -21 。 PAST #8 を解いて考察を書いている。

rust365 (2021-05-14) は its をつくっている。あまり進んでいない。

スーパーマリオ オデッセイはコンプリートに向けて進めている。

『セキュア・バイ・デザイン』はあまり進んでいない。

2022-W04 の目標

第八回 アルゴリズム実技検定 (PAST) K - ニワトリのお見合い を解いた

第八回 アルゴリズム実技検定 (PAST) K - ニワトリのお見合い を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_k

全探索はできそうにない。S の各行からうまくひとつずつを選ぶ……とか……？ DP ？ 過去に選んだものを保持するのが厳しそうだ……。そんなことを考えたものの諦めて解説を読んだ。

解説: https://atcoder.jp/contests/past202109-open/editorial/2727

重み最大化二部マッチングの問題。ネットワークフロー。本では何度か見ているんだけど解ける気がしない。 2 の最小費用流に帰着して解く方法で解いた。

https://qiita.com/drken/items/e805e3f514acceb87602 も合わせて読んだけど。まだ解ける感じがしない。

提出: https://atcoder.jp/contests/past202109-open/submissions/28670632

歯医者に行った。

今日のコミット。

第八回 アルゴリズム実技検定 (PAST) J - 数列の反転 を解いた

第八回 アルゴリズム実技検定 (PAST) J - 数列の反転 を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_j

指定した位置の値を出力するクエリ (出力操作) と指定した範囲を反転させるクエリ (反転操作) がある。

指示通りに実装すると、数列全体の反転操作を何度も要求されたとき 10^10 になってしまい間に合わない。何かしら工夫が必要になる。

反転操作は何度繰り返したとしても、ある位置 i (0 <= i < 2 * N) で出力される値は i + 1 か 2 * N - i かの 2 種類しかない。値は位置と反転されているかで決まる。反転されているかはある位置を含む反転操作が奇数回かで決まる。

反転操作は区間なので区間加算を処理できると良さそうだ。区間加算は BIT やセグメント木を 2 つ使うか遅延セグメント木で処理できる。……がちょっと考えてみるとそこまでする必要もない。

反転操作は左右対称なので左半分があれば良い。右半分が問題になったときは反転した左半分の位置だと考えると同じことになる。そこで左半分で考える。ある位置が反転されているかを知りたいときはその位置よりも左側から中央までの反転が奇数回かが分かると良い。ある位置より左側を対象とした反転が何回あるかを取れると良い。つまり 1 点加算と区間和を高速で処理できると良い。

今回は BIT を使用した。

反転操作と左右対称の 2 箇所で反転しているので混乱する。現状の全体を出力する関数を途中まで使って壊れていないかを確認した。

今日のコミット。

第八回 アルゴリズム実技検定 (PAST) H - 最短経路を解いた

第八回 アルゴリズム実技検定 (PAST) H - 最短経路 を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_h

N 頂点の重み付きの木において「最短距離が X になる相異なる頂点の組」が存在するかを求める。 N <= 3000 。

まずは全探索を考える。すべての頂点の組について最短距離を求められるか。ワーシャル・フロイド法だと O(V^3) で間に合わない。各頂点についてダイクストラ法はちょっと間に合わないか。ギリ間に合うかもしれない。

木であることを活かせる方法はないか考える。木における任意の 2 頂点 u, v の距離は頂点からの距離を dist 共通の祖先を lca とすると dist[u] + dist[v] - dist[lca] * 2 の形で O(1) で求められる。 lca の計算はダブリングで前処理 O(NlogN) とクエリ O(logN) 。これで O(N^2 log N) で間に合う。

実装を進める過程で思い出したことには、木における距離は DFS で O(N) で求められる。ひょっとしたら各頂点から DFS でも間に合ったかも……。 → 解説を見たらこの方法で O(N^2) が正解だった。

ちなみにダイクストラ法でも間に合った。 PAST 本番だったらペナルティも大してないのでとりあえず投げてみたかもしれない。

今日のコミット。

一日中寝ていた

昨日に続いて一日中横になっていた。まだお腹の調子がおかしい。陀羅尼助丸を飲んでまた寝る。

今日もまた最低限のノルマのみこなしている。リングフィットアドベンチャーは諦めている。

今日のコミット。