モラトリアムライフ

自由を求めて

精進記録 : Codeforces Round #346 Div2 F. Polycarp and Hay

問題概要

n \times m の2次元数列 A = \{ a_{i, \, j} \} \, (1 \leq i \leq n, 1 \leq m) が与えられる.
このとき, 次の条件を満たすような n \times m の2次元数列 B = \{ b_{i, j} \} を求めよ. (存在しないなら "NO" を出力せよ)

  • b_{i, j} は整数
  • 0 \leq b_{i, j} \leq a_{i, j} (1 \leq i \leq n, 1 \leq j \leq m)
  • B の総和が k と一致する, すなわち \sum_{b \in B} b = k
  • ある A の要素 a_{i, j} \in A が存在して, a_{i, j} = b_{i, j} かつ すべての b \in B に関して「 b = 0 または b = a_{i, j}」が成り立つ.
  • b \neq 0 なる B の要素は グリッド上連結である.

    制約

  • 1 \leq n, m \leq 1000
  • 1 \leq k \leq 10^{18}
  • 1 \leq a_{i, j} \leq 10^{9}
  • 入力はすべて整数

codeforces.com

考察

答えが存在する場合について考える. そのとき, 上記の4, 5番目の条件を満たすような a_{i, j} がわかっているとすると, DFSやBFSなどによって簡単に答えを求めることができる. ( a_{i, j} 以上となるような要素に向かって探索範囲を広げていく)
したがって, そのような a_{i, j} を求めることがこの問題の本質である. そこでまずは, どのような条件が満たされていれば良いかを考える.
b = a_{i, j} となるようなものの数を m とすると 3番目の条件から m \cdot a_{i, j} = k であるから, m = \frac{k}{a_{i, j}} であり, また, m は整数であるから a_{i, j} は k の約数である必要があることが言える.
つまり

k の約数であるような a_{i, j} であって, a_{i, j} 以上となる (i, j) との連結成分の個数が \frac{k}{a_{i, j}} 以上 となるような a_{i, j} は存在するか? 存在するならば1つ求めよ.


という問題を考えることになる (逆に, この条件が成り立っているならばBFS, DFSで構成可能)

しかし, 各 a_{i, j} が条件を満たしているかをBFS, DFSなどで確認すると 1回に O(nm) かかってしまい全体として間に合わなくなってしまう. (多分) それゆえ, 全体として連結成分を数える時の計算量を落としたい. そこで, 個人的によく使っている考え方を示すと (※ 個人の感想です)

  • 情報を丸める : (ex : 平均値, 総和だけの情報しかいらない等の各数列の情報全てを必要としない場合)
  • 過去の情報(履歴を用いる).
    • ある単調性が成り立つ場合 → (ソートをしてから)過去の情報を用いて計算,情報を逐次更新 (ex : 尺取り法)
    • 「組合せ数」や「可能か不可能か」などの情報が比較的軽い場合 → 動的計画法 DP を行う
  • 強いデータ構造で殴る！(Segment木, 遅延伝搬Segment木, Rolling Hash, Link Cut木, HL分解 etc... )

今回は, a_{i, j} 以上となる要素の連結要素を知りたい！ということであったので, f(x) を x 以上となるような(連結の情報を含む)二次元配列のデータとすると, 雑な記法をすると a_{x_{1}, y_{1}} \leq a_{x_{2}, y_{2}} \longrightarrow f(a_{x_{1}, y_{1}}) \supseteq f( a_{x_{2}, y_{2}} ) という "単調性" が成り立つので a_{i, j} が 大きい順にソートして Union Find で連結成分を更新しながら判定をして行けば良い. (2次元グリッド上でUnionFind木を使う)

実装例

codeforces.com

精進記録 : Educational Codeforces Round #56 G - Multidimensional Queries

問題概要

n 個の k 次元上の点 a_1, a_2, ..., a_n \in \mathbb{Z}^{k} が与えられる.
このとき, q 個の次のクエリに答えよ.
　　　1. i \in \mathbb{N}, b \in \mathbb{Z}^{k} が与えられる. a_i を b に変更する.
　　　2. l, r \in \mathbb{N} \, \, (\, l \leq r\, ) が与えられる. マンハッタン距離1の最大値 \displaystyle{\max_{ l \leq i, j \leq r} \, || a_i - a_j ||_{1}} を出力する.

制約

  • 1 \leq n \leq 2 \cdot 10^{5}
  • 1 \leq k \leq5
  • 1 \leq q \leq 2 \cdot 10^{5}
  • 1 \leq l \leq r \leq n
  • -10^{6} \leq a_{i, \, j} , b_{i, \, j} \leq 10^{6} (1 \leq i \leq n , 1 \leq j \leq k)

問題リンク codeforces.com

考察

愚直に考えると、変更は O(k) , 最大値を求めるのに全てのペアに調べると O(k n^{2}) がかかってしまい, 到底間に合わない(特に, 最大値を求める部分). そこで k が 5以下という非常に小さい制約があることから, おそらくこれを利用して, 最大値を求める部分を高速に処理できればよいだろうと考えられる(今持っている情報を k に載せたい).

さて, ここでマンハッタン距離について一度考えることにしよう.

\displaystyle{ || x - y ||_{1} = \sum_{i = 1}^{k} |x_{i} - y_{i}| }

マンハッタン距離は絶対値が含まれているため、一つの点を固定したときに、その固定した点の各成分が正として振る舞うのか, それとも負として振る舞うのかはもう一点との関係によって定まってくる. それゆえ距離の最大値を求める際に, 各点の情報が2次元的に必要になるように感じられる.

しかし, もし絶対値がなければどうだろうか. 2点間の成分の和の最大値というのは, 各点の成分の和の最大値と最小値が分かれば容易に求めることができる(ある種1次元的な情報に落とし込める). そして, これは点更新セグメント木を使って更新, クエリともに O(\log n) で高速に処理することができる.

\begin{aligned} \max_{x, y \in S} \sum_{i=1}^{k} (x_{i} - y_{i} ) &= \max_{x \in S} \sum_{i = 1}^{k} x_{i} + \max_{y \in S} \left (-\sum_{i = 1}^{k} y_{i} \right) \\ &= \max_{x \in S} \sum_{i = 1}^{k} x_{i} - \min_{y \in S} \sum_{i = 1}^{k} y_{i} \end{aligned}


元の問題に視点を戻すと, 求めるられているのは絶対値の和である. どのようにして求めることができるだろうか. それは 各成分を正負の方向に移動させた空間上で、上の値を求めることである. なぜなら 一般に実数 a に対して a \leq |a| かつ -a \leq |a| であるので, 任意の数列 a_1, a_2, ... に対して, 少し雑な記法を許すと \sum_{i} \pm a_{i} \leq \sum_{i} |a_{i} | が成り立つからである. 2

正負の方向を bit列で管理して (これは高々 2^{5} = 32 個) 最大値と最小値の差を求めるセグメント木を使って全方向を探索すれば、このクエリに O(2^{k} \cdot \log n) で答えることができ、更新も O(2^{k} \cdot (k + \log n)) で十分高速に行うことができる. これにより、この問題を解くことができた

実装例

codeforces.com

  1. マンハッタン距離とは L1 ノルムのこと. a \in \mathbb{R}^{k} に対して || a ||_{1} = \sum_{j = 1}^{k} |a|. 各成分の絶対値の和↩

  2. より正確には, 「上記によって下から抑える. また a = |a| \land -a = |a| が成り立つので 等号を与えるような各成分への正負の方向が存在する」のでこれを全探索することにより求められる.↩

入青

青色コーダーになりました

AtCoderのレートが1600を超え、青色コーダーになれました.
Codeforcesのレートも現在、青であるので青々しく競プロをやれています.
f:id:mathematicsian:20191112230308p:plain 新ABCになり, ratedの回が多くある中, 若干才能の限界を感じつつも, 少しづつ精進を重ねた結果何とか入青できました. ここからレートをあげるのはそれなりに大変なことであり, そもそも現状維持ですら危ういので精進をより積み重ねて大学卒業までに1800以上を目指せるように頑張りたいです.

yukicoderのNo.822 Bitwise ANDをACした

問題はこちらから

yukicoder.me

問題概要

x & y = N かつ y - x \leq Kを満たす整数の組 (x, y) の個数を求めよ (無限個の場合はINFと出力)

制約

0 \leq N \leq 10^{5} かつ 0 \leq K \leq 300

考察

まず, 無限個になる場合を判定したい. 大きくなるほど, 差は多くなると考えられる.
y の最上位ビットとして N の最上位ビットよりも大きな t ビットが立っているときの差の最小値は y をできるだけ増やして, xをできるだけ小さくしたい. したがって, i = 1 ~ ( t - 1 ) ビット目を K の i ビットが立っているなら, x, y ともに1, 立っていないなら x は1, y は 0 とすればよい. この差の最小値は 2^{t-1} | N- (2^{t-1} - 1) = N+1 だから, K と N+1 の大きさを比べれば良い.

K \geq N+1 のとき

x, y を上記の作り方をすれば無限個存在する.

K < N+1 のとき

上記議論から, t ビットが立っているような t の数は高々有限個. したがって, 有限個の組しか存在しない また, andの性質から x, y はともに N よりも大きく, かつ N の最上位ビット以上のとこにビットがあってはならない. これを全探索すれば良い！

解答

yukicoder.me

自分語りと最近の振り返り

決断

弊学では, 2年から3年に上がる時に90単位以上取得してGPTというものが3.00↑すると 早期卒業の仮認定が受けられるんですが, それに該当したため3月の間少し悩みました( 結論は, 使わないことにしたんですけど)

理由

権利を行使しなかった理由としては, めんどくさい, 周りと離れたくない, 英語に自信がないというのが主な理由です. 一番大きい理由は「周りと離れたくない」; 金銭面を考慮しても, はじめは使う気があったんですけど, 周りの人と離れるのが嫌だなって感じてやめました. 入学当初は, 自分はかなりプライドが高い人間であったこともあり, この大学に不満がありつつも入学した時には早期卒業でも使って さっさとこの大学から脱出したいなぁなんてことを考えていました. しかし, 人間というものは大して変われる生き物ではないのだなと実感させられます. 怠け癖であったり, 一歩踏み出せない, 決断を下せないなんてことは, その人間の生まれた時から持つ性であるのだと. だから, しない変わりに大学生活を充実させよう, 社会に適応できるように変わらなければいけないな, なんてことをいくらか考えていました...

実際の変化

特にありませんでした. 掲げた目標に向かっていけるような人間であったら, 僕が今置かれているような惨めな惨状には至らないということが背理法によって示されます. そして, 今も変わらないとなぁと考えつつも, なんらひとつも行動に移しません.

その他

水色Coderになりました(水色最底辺)
今年中に青色になれるようにある程度進捗を生みたい.
競プロであったり, 数学であったりするものは起電力が低いので, 僕なんかにも"ある程度"の進捗ができる面白いもの(嬉しい)
それと英語大苦落単しそう(落単童貞卒業か？)

属する区間(メモ書き)

互いに素な区間 I_k (k = 0, 1, 2, ..., n-1) (つまり, i \neq j \Longrightarrow I_i \cap I_j = \emptyset)に関して
\displaystyle{U := \bigcup_{0 \leq k ＜ n}^{} I_k} 上の点 x \in U が属する区間 I_m を(O(\log n) のオーダーで)求めるには,
std::set に pair<int, int>で区間を保持しておいて, make_pair( xのindex, INF)を"upper_bound"メソッドで探して得られるイテレータを1つ前に戻せば良い

入力から区間が変わらない静的な場合は, std::vectorをソートしたものを二分探索を行なっても良い(メモリ効率自体はこちらの方が良い)

属する区間(メモ書き)

互いに素な区間 I_k (k = 0, 1, 2, ..., n-1) (つまり, i \neq j \Longrightarrow I_i \cap I_j = \emptyset)に関して
\displaystyle{U := \bigcup_{0 \leq k ＜ n}^{} I_k} 上の点 x \in U が属する区間 I_m を(O(\log n) のオーダーで)求めるには,
std::set に pair<int, int>で区間を保持しておいて, "upper_bound"メソッドで得られるイテレータを1つ前に戻してやれば良い

入力から区間が変わらない静的な場合は, std::vectorをソートしたものを二分探索を行なっても良い(メモリ効率自体はこちらの方が良い)