たれながし

色々雑多に書きます

緑diff精進 その5 (2/19)

近況報告

ここ最近このブログどころか、精進がほとんどできていなかった。というのも、自分は今修士1年でつい先日まで研究の中間発表の準備に取り組んでいたのと、就活の面接ラッシュでなかなか趣味に時間が取れない状況だった。 とはいえ中間発表も無事に終え、就活もだいぶ満足する形で終えられたので、今週からは精進する時間がしっかりと取れそうである。入水目指して頑張りたいね。

さて、AtCoderの現在のレートは1111(ゾロ目！)になった。直近4回のうち、2回は勝利、2回は変動ほぼ無しといった感じで安定感ある結果を残せている。 特にABC340については初めて6完できたし、ABC341では遅延セグ木をちゃんと使いこなせたのでとても成長を感じている。精進してないけど。

2/20現在のatcoderのレート

ところで、この緑diff精進についてだが、今回からRust中心で解いていこうと思う。やっぱABC341 EでPythonで書いた遅延セグ木がTLEし、Rustで書き直したら300ms台でACできた経験が大きい。再帰や遅延セグ木で殴れるがTLEが怖いなぁというお気持ちがやっぱ辛いので、制約が厳しい問題向けにRustの習熟度を上げていきたい。(あとRustで解ける問題は(BTreeSetとか使わなければ)大体Pythonでも楽に解けそうなので)

解いた問題

  • ABC016 C - 友達の友達
  • ABC311 D - Grid Ice Floor
  • ABC075 C - Bridge
  • ABC124 D - Handstand
  • ABC057 C - Digits in Multiplication
  • ABC293 D - Tying Rope
  • ABC334 E - Christmas Color Grid 1
  • ABC273 D - LRUD Instructions

ABC016 C - 友達の友達

atcoder.jp

感想 (解答中に考えたこと)

  • なんかめちゃくちゃ制約が緩いので、とりあえず全探索すれば良い

提出コード

atcoder.jp

ABC311 D - Grid Ice Floor

atcoder.jp

感想 (解答中に考えたこと)

  • 無難にBFSが通りそう。停止した位置についてBFSして、使ったマスを埋めていく。

提出コード

atcoder.jp

ABC075 C - Bridge

atcoder.jp

感想 (解答中に考えたこと)

  • 過去に解いた記憶があるが…… UnionFindで橋判定したいもの以外を繋げて、sameかどうかを見れば橋かどうかがわかる。

提出コード

atcoder.jp

ABC124 D - Handstand

atcoder.jp

感想 (解答中に考えたこと)

  • 最近のABCでセグ木の問題の設定に似てる。反転操作は境界部分を持てば区間更新を1点更新にできる。
  • よく読んでみるとそんな難しいことしなくても良さそう。ランレングス圧縮したあとの Sは必ず...01010101...という格好になるので、[10101...01]のような区間で、0が K個含まれていてかつこの区間が最長なものを出力してあげれば良い事がわかる。しゃくとり実装すればok。

提出コード

atcoder.jp

ABC057 C - Digits in Multiplication

atcoder.jp

感想 (解答中に考えたこと)

  • Nの制約がちょっと大きい。とはいえ N = A \times Bなので、 Aについて全探索すればせいぜい 10^5回の計算なので通る。

提出コード

atcoder.jp

過去解いてたらしい(覚えてない)

ABC293 D - Tying Rope

atcoder.jp

感想 (解答中に考えたこと)

  • これは解いた記憶がある。ロープに色が云々言っているが、つまり2頂点がとある辺で繋がっているグラフが N個与えられていて、それを M個の辺で繋ぐことを考えれば良い。
  • ある頂点は3つ以上の辺を持たないことは問題の制約により言えるので、環状の判定はUnionFindで繋ぐ際にsameかどうかを判定すれば良い。

提出コード

atcoder.jp

ABC334 E - Christmas Color Grid 1

atcoder.jp

感想 (解答中に考えたこと)

  • これはそもそも出たコンテストの問題ですね。緑のマスをUnionFindで繋げて、赤のマスが緑になった際にUnionFind#groupsの長さがどう変化するかを考えてあげれば良い。
  • 4方のマスを新たなUnionFindで繋げて、groupsの長さを見れば繋げた際にいくつ緑の連結成分数が変化するかが求められる。

提出コード

atcoder.jp

コンテスト中はUnionFindで繋げず、各緑の連結成分にid振ってたらしい。

ABC273 D - LRUD Instructions

atcoder.jp

感想 (解答中に考えたこと)

  • どうせ愚直シミュレーション……と思い制約を確認してみるとあまりにも大きすぎてひっくり返った。
  • 結局これはある進行方向に対して、直近の壁はどこにあるのかを求めることができれば良い。
  • 縦軸・横軸毎にHashMapを用意し、各要素ごとにBTreeSetで壁の情報を追加する。進行方向は4方位のどれかなので、現在地点から進行方向にある壁のBTreeSetについて二分探索で直近の壁を求めてあげればなんとかなる。

提出コード

atcoder.jp

Rustでセグメント木に乗せる際のメモ

Rustで競プロしててセグメント木・遅延伝搬セグメント木を使いたいことってありますよね。 大体ac-library-rsに実装されているものを使うと思うんですけれど、MonoidやMapMonoidというモノイドの実装をする必要があり、割と大変そうなので自分用にメモを残します。 (大嘘担当大臣していたらひっそりと教えてください)。

TL;DR

  • たぶんこれを読むのが一番はやい(わかりやすい)と思います。 betrue12.hateblo.jp

セグメント木

Monoidトレイトを継承した構造体を実装します。

struct MyMonoid;
impl Monoid for MyMonoid {
    type S = usize; // セグ木自体に乗せるオブジェクトの型
    fn identity() -> Self::S {
        // 単位元
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        // 演算操作
    }
}

fn main() {
    let mut tree = Segtree::<MyMonoid>::from(vec![0; N]); // こんな感じに定義
}

usizeにおける加法の実装例

struct Add;
impl Monoid for Add {
    type S = usize;
    fn identity() -> Self::S {
        0_usize
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        a + b
    }
}

fn main() {
    let mut tree = Segtree::<Add>::from(vec![0; N]);
}

atcoder.jp

ちなみに最大・最小・加法・乗法についてはビルトインで実装済みなので、それを利用するのが賢いと思います。

遅延伝搬セグメント木

概要

  • 区間更新・区間クエリを効率的に捌ける便利なデータ構造
  • 計算量
    • 構築: O(N)
    • 区間更新・区間クエリ: O(\log N)
      • 定数倍が遅いので注意が必要。
  • 各ノードは以下の情報を持つ
    • data: S
    • lazy: F
      • 子ノードの遅延している更新情報
  • 以下の演算の定義が必要
    • binary_operation: (S, S) -> S
      • data同士の演算操作
    • mapping: (F, S) -> S
      • 親(あるいはクエリ)からの更新情報 F を自分のノードのdataに作用させる演算操作
    • composition: (F, F) -> F
      • 親(あるいはクエリ)からの更新情報 Fを子ノードに伝える必要がある場合に、lazy同士を合成する演算操作
        • 複数回の更新操作を1度の更新操作にまとめるという意味
        • (新しい操作 f, 過去の操作 g)になる。つまり f\circ g(x) =f(g(x))という事ですね。
  • 区間更新
    1. 更新情報 F を受け取り、過不足なく区間を覆える要素にmapping操作でdataを更新する
    2. 子ノードが存在する場合、自身が持つlazyと更新情報Fをcomposition操作で更新する

利用方法

MapMonoidを継承したクラスを構造体を実装する。

struct MyMapMonoid;
impl MapMonoid for MyMapMonoid {
    type M = MyMonoid; // 通常のセグメント木で使うモノイドの情報 data同士の操作やdata自体に関する定義
    type F = usize; // 遅延更新情報の型
    fn identity_map() -> Self::F { // 遅延更新情報の単位元
        0_usize
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        // 親ノードor区間更新クエリから渡された更新情報(F)を自身が持つdata(S)に作用させる演算操作 ((F, S) => S)
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        // 親ノードor区間更新クエリから渡された更新情報(F1)を子ノードへ伝える更新情報(F2)とマージさせる演算操作 ((F, F) => F)
    }
}

usizeにおける加法の実装例

struct MapMax;
impl MapMonoid for MapMax {
    type M = Max<usize>;
    type F = usize;
    fn identity_map() -> Self::F {
        0_usize
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        *f.max(x)
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        *f.max(g)
    }
}

fn main() {
    let mut lazyTree = LazySegtree::<MapMax>::from(vec![0; W]);
}

atcoder.jp

lazyに区間長を持たせたい場合

mappingの引数に区間長が与えられていないため、区間更新で"範囲内の要素に +aする"みたいなことができなさそう。 しかしセグ木に乗せるデータ構造を以下のように工夫すればうまくいく。

#[derive(Clone)] // Cloneのサブクラスである必要がある
struct MyData {
    value: usize,
    length: usize
}

fn main() {
    let mut lazyTree = LazySegtree::<MyMapMonoid>::from(vec![MyData { value: 0, length: 1 }; N]); // 利用するデータの範囲にlength=1を与えないとvalueが更新できない
}

struct MyMonoid;
impl Monoid for MyMonoid {
    type S = MyData;
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        MyData {
            value: a.value + b.value,
            length: a.length + b.length
        }
    }
    fn identity() -> Self::S {
        MyData { value: 0, length: 0 }
    }
}
struct MyMapMonoid;
impl MapMonoid for MyMapMonoid {
    type M = MyMonoid;
    type F = usize;
    fn identity_map() -> Self::F {
        0_usize
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        MyData {
            value: x.value + f * x.length,
            length: x.length
        }
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        f + g
    }
}

cf. AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

緑diff精進 その4 (1/26)

解いた問題

  • ABC045 C - Many Formulas
  • ABC102 C - Linear Approximation
  • AGC005 A - STring
  • APC001 B - Two Arrays
  • ABC114 C - 755
  • ARC140 B - Shorten ARC

ABC045 C - Many Formulas

atcoder.jp

感想 (解答中に考えたこと)

  1. evalで解けてしまいそうだが、本質じゃないので使わない。
  2. 各数字がどの桁で幾つ現れるかを考えれば良い。
  3. 基本的にどの数字も n桁目は 2^{|S|-n-3}\left( = C(n)\right)個現れる。ただし C(n)を現れる回数とする。
  4. また各数字が使える回数は数式のパターンの数分なので 2^{|S|-1}で、 Sにて k桁目であった数字が k+1桁目以降に現れるはずがない。よって k桁目の数字を S_{k}として、その寄与は \sum_{n=1}^{k-1}S_{k}\times 10^{n-1}\times C(n)\;\left(k\geq 2\right)。最後に S_{k}\times\left(C(k) - \sum_{n=1}^{k-1} C(n)\right)\times 10^{k-1}の分を補正すれば良い。

提出コード

まぁbit全探索で良い atcoder.jp

ABC102 C - Linear Approximation

atcoder.jp

感想 (解答中に考えたこと)

  1. 絶対値の和の最小化なので、どうせ中央値あたりを考えれば良さそう。
  2. \sum |A_{i} - b - i| = \sum | B_{i} - b |のように変形すれば、 B_{i}の中央値を求めれば終わり。

提出コード

なんと、 B_{i}のソートを忘れていたらしく……(3WA) しかし数列の長さが偶数のケースを無視していたが、通ってしまった。 atcoder.jp

AGC005 A - STring

atcoder.jp

感想 (解答中に考えたこと)

  1. 左から消去っていうのが効いてきそう？とりあえずランレングス圧縮する。
  2. 左端の文字がTである場合は無視すれば良いので、Sから始まる文字列のみ考えれば良い。
  3. n個Sが連なっているものを S(n)、Tが連なっているものを T(n)とする。
    • S(n)T(m)\;\left(n\leq m\right)であれば、消去操作は n回
    • S(n)T(m)\;\left(n\geq m\right)であれば、消去操作は m回で、次のSのまとまりの個数に n-mを加える。
  4. |X| - 消去回数\times 2が答えになる。

提出コード

左から捜索して特定の文字列になったら削除はStackで管理、めちゃ典型だ……。 atcoder.jp

APC001 B - Two Arrays

atcoder.jp

感想 (解答中に考えたこと)

  1. APCなんてものがあるんですね……。 c_{i}=a_{i}-b_{i}で表される c_{i}からなす数列 Cを考える。ここで操作は以下のように言い換えられる。
    • i, j \in \left[1, N\right]を選び、 c_{i}に2を加算。 c_{j}に-1を加算。
    • 上の操作によって全ての c_{i}を 0にすることが目標。
  2. このことから x=-\sum_{i=1}^{N}c_{i}としたとき、 xが操作回数になる。これ以上操作をすると Cの和が1以上になるので一致することはなくなる。同様に x未満の操作回数でも一致しない。
  3. Cの各要素から最短で 0にする方法を考える。また、 +2する回数と -1する回数を分けてカウントする。
  4. c_{i}が正数であるならば、 -1をその数だけ繰り返せば良い。
  5. c_{i}が負数であり、偶数であるなら +2をその数/2回繰り返す。奇数ならば(その数+1)/2回 +2を繰り返した後に -1を1回行う。
  6. 最後に +2と -1の回数および xから判定をする。
    • -1の回数が +2よりも大きければNo
    • +2の回数が -1よりも大きい場合、余剰分を +2を1回と +1を1回で繰り返せば Cの要素は全て0になる必要条件を満たし、操作回数が xと同じになればYes
    • その他回数が同じだった場合や xが負数の場合の処理を書けば良い

提出コード

ABC114 C - 755

atcoder.jp

感想 (解答中に考えたこと)

  1. 上位の桁を固定しながら和を取るのが簡単そうだが、同様のもので桁DPがある。練習がてら桁DPで解いてみる。
  2. dp(i, j, k):=上から i桁目を見た時、数字の使われ方が状態 j (ビット)である場合の数。ただし kは上位 i桁目まで一致しているかどうかのbool値。
  3. 上位の桁を0埋めする場合が考えられ、また3057のように途中に0を入れてはいけないので、bitで探索するときも0のみ特別に扱う必要がある。
  4. あとは i桁目の数字と jの状態から丁寧に丁寧に丁寧に状態遷移を実装してあげれば良い。

提出コード

苦しすぎた…… atcoder.jp

ARC140 B - Shorten ARC

atcoder.jp

感想 (解答中に考えたこと)

  1. ARCであればどのタイミングで操作してもよく、AARCCであれば奇数回目で操作すると偶数回目でACまで変化できて嬉しい。つまりAARCCとARCの個数がわかればよいのでは？ -> WA
  2. 考えてみたがわからんので解説をチラ見。なるほど、A...ARC...Cを常に奇数回目で操作するようにすれば、両端のAあるいはCの個数の小さい数ぶん操作が可能になる。
  3. つまりランレングス圧縮する過程でA...ARC...Cの塊の情報を整理すれば見通しが良くなりそう。
  4. あとは奇数回目であればARC以外のものを優先して操作し、偶数回目であればARCを優先して操作することが必要になる。
  5. 実装方法に迷ったが、操作回数は高々 N回で抑えられるだろう(操作することにより、1文字あるいは2文字消去なので)。なのでpriority_queueを使って愚直に勘定するのが良い。

提出コード

atcoder.jp

緑diff精進 その3 (1/25)

解いた問題

  • ABC052 D - Walk and Teleport
  • ABC053 D - Card Eater
  • ABC239 E - Subtree K-th Max
  • ABC276 E - Round Trip
  • ABC177 E - Coprime
  • ABC115 D - Christmas
  • ABC194 E - Mex Min

ABC052 D - Walk and Teleport

atcoder.jp

感想 (解答中に考えたこと)

  1. 貪欲かDP。DPは制約的に無理そうなので貪欲の方針にする。
  2. 1------2-3-4 みたいな町で B = A + 3くらいの条件で考えてみると、234のまとまりにテレポートした方が良い。また、3にテレポートして 3 -> 2 -> 3(経由) -> 4とすると2 -> 3(経由)分が無駄になるので、一番近い場所にテレポートするのが良い。
  3. よって \rm{dist}_{i} = X_{i} - X_{i-1}として、 \sum_{i=2}^{N} \min \left\{\rm{dist}_{i} \times A, B\right\}で良さそう。

提出コード

atcoder.jp

ABC053 D - Card Eater

atcoder.jp

感想 (解答中に考えたこと)

  1. 何を消すかを管理すれば良い？
  2. 同じカードの枚数が偶数ならば2枚、奇数ならば1枚残る。
    • 操作の対象はカードの枚数を Mとして M \geq 3であって、操作1回につき2枚ずつ減るので
    • この時の操作の回数は \lfloor \frac{M-3}{2} \rfloor + 1 \; \left(M \geq 2\right)
  3. 偶数枚あるカードの種類の数を Lとする。
    1. Lが奇数のときは1枚まで減らせるため、残った1枚を最小あるいは最大とできるように3枚を選択すれば良いので、操作回数は \lfloor \frac{L}{2} \rfloor + 1。
    2. Lが偶数の時は2枚まで減らせる。ここでこの2枚を同時消しできる可能性があるので、偶数枚あるカードのうち最小値 L_{\rm{min}}および最大値 L_{\rm{max}}を残すように選択する。 \left(L_{\rm{min}}, L_{\rm{max}}\right)に含まれる奇数枚のカードが存在すれば操作回数は \lfloor \frac{L}{2} \rfloor。存在しなければ \lfloor \frac{L}{2} \rfloor + 1
  4. 操作回数を Kとすれば、 N - K \times 2が残るカードの枚数。

提出コード

atcoder.jp

ABC239 E - Subtree K-th Max

atcoder.jp

感想 (解答中に考えたこと)

  1. Kの制約がそこまでキツくないので、部分木を O(1)で出力できれば十分そう。
  2. 木はとりあえずlist[set[int]]で管理し、根からBFSで子 -> 親のパスを消し飛ばしておく。
    • これは不要で、DFSの引数に親を追加し、親 = 子の場合にcontinueすれば良い。
  3. DFSで根から探索し、各ノードに上位20件の数字のリストを持たせていく。
    • つまり葉であれば[X[n]]を返し、そうでなければ子ノードの返り値とX[n]を合わせて降順ソート & limit = 20で良い
  4. あとは O(1)で答えが出る。テーブルの構築にはDFSでの構築部分とクエリ部分で O(Q + NK\log K)かかってると思う(たぶん)。

提出コード

部分木といえばオイラーツアーがあったなと反省……。 atcoder.jp

ABC276 E - Round Trip

atcoder.jp

感想 (解答中に考えたこと)

  1. BFSでvisitedがTrueのものがあればYes? しかし戻るパターンを除去するのが面倒くさい。
  2. だらだら実装してサンプルが合わないので解説を少しだけ読む。色分けかぁ……これは思いつきたい。
  3. visitedをbooleanではなく数値で管理し、Sを#扱いにして4方向にBFSするだけになった。

提出コード

atcoder.jp

ABC177 E - Coprime

atcoder.jp

感想 (解答中に考えたこと)

  1. setwise coprimeはgcd(*A) == 1で一発で判定可能。つまりpairwise coprimeの判定が肝になる。
  2. 当然のことながら全探索は無理。ところで、 \gcd{\left(a, b\right)} =1って \frac{a}{b}が既約分数なので、共通の素因数を持たないと解釈できそう。
  3. つまり集合 Aの素因数を全部調べて重複があるかを判定すれば良い。
  4. エラトステネスの篩をつかって \max{\left\{A_i\right\}}\left(=A\right)までの素数を列挙し、素数をkeyとしてkeyが素因数として出てきたかを持つboolをvalueとして持つHashMapを用意する。素因数分解は O(\sqrt{N})のものを使う。素因数分解については指数の要素はいらないので、素因数の集合を返すように改造しておく。
  5. あとは出てきた素因数をHashMapに記録し、既にTrueのものがあればpairwiseになる。
  6. これ計算量 O(N\sqrt{A})で 10^9じゃないですか？落ちそう -> ACした。

提出コード

エラトステネスの篩で素数を列挙している途中で、 D\left[n\right]:=nを落とした素数とすることで試し割り(2 ~ \sqrt{N}まで割る方法)をする必要がないので O(\log A)でできるらしい。天才では？？？？ atcoder.jp

ABC115 D - Christmas

atcoder.jp

感想 (解答中に考えたこと)

  1. 明らかに再帰関数の実装を求めていそうな問題。とはいえバーガーの高さとパティの枚数は普通に漸化式を解けば O(1)で出る。
  2. レベル nバーガーをg[n]、バンズをB、パティをPとすればレベル nバーガーはBg[n-1]Pg[n-1]Bと書ける。
  3. レベル nバーガーに対して、 Xが下部のレベル n-1バーガーの領域を超えている場合のみその分のパティを加え、その分の高さを Xから引いていけば求まる。
    • レベル kバーガーの区切りが良いところから始める必要があるので。真ん中のパティを特別に扱わないとバグる。
    • パティが存在する領域よりも高い Xである場合、レベル0バーガーの探索を終えても Xは0よりも大きくなるので、ループの条件に レベル >= 0が必要 (1敗)

提出コード

正直上記の説明じゃ何も伝わってないと思う……説明難しい……。 atcoder.jp

ABC194 E - Mex Min

atcoder.jp

感想 (解答中に考えたこと)

  1. しゃくとりっぽく、区間をずらした際に出ていく数字・入る数字を管理すれば高速で \rm{mex}求められそうじゃない？(根拠なし)
  2. 使える数字をSortedListで管理し、区間にある数字をHashMapで管理する。区間にある数字について、個数が0になったものがあればSortedListにその数字を追加し、個数が1以上になったものがあればSortedListからdiscardする。
  3. あとはSortedListの先頭をchminすれば良い。これで計算量は O(N\log N)なはず。定数倍の遅さにビビりながらsubmit。

提出コード

atcoder.jp

緑diff精進 その2 (1/24)

解いた問題

  • ABC260 D -Draw Your Cards
  • ABC075 C - Bridge
  • ABC191 C - Digital Graffiti
  • ABC166 E - This Message Will Self-Destruct in 5s
  • ABC194 D - Journey
  • CodeFestival 2016 qual A C - Next letter

ABC260 D -Draw Your Cards

atcoder.jp

感想 (解答中に考えたこと)

  1. 愚直にシミュレーションする問題っぽい。場を表す配列を容易したとして、何も考えずに実装すると O(N^2)で間に合わない。
  2. 要求されるデータ構造は、場に見えるカードの数を管理していて、ある数 X以上で最小の数を O(N)よりも速く見つけられるようできるもの。
  3. 後者の条件は二分探索でいけそう。つまり、SortedListで場に見えるカードの種類を管理し、実際の束はHashMapで管理するとうまくいきそう。
  4. 二分探索はSortedListのbisect_leftを利用する。これによって O(N\log{N})で解ける。
  5. 実装したがTLE。というのもhashmap[key] = hashmap[otherkey] + [new_value]としたところが遅いようだった。hashmap[key] = hashmap[otherkey]の後にhashmap[key].append(new_value)をするとACした。
    • 以下のように初期化と一緒にappendっぽいことをしようとすると参照渡しじゃなくなる。まぁhashmap[0] + [7]で新しいリストに変わってるのは確かに納得。

hashmapのid変化の確認

提出コード

atcoder.jp

ABC075 C - Bridge

atcoder.jp

感想 (解答中に考えたこと)

  1. UnionFindっぽい雰囲気。特定の辺を除いてmergeしたあとにグループの数が2以上かどうかで判定可能。
  2. 成約がとても緩いので、各辺を選択してからそれ以外の辺を結んで判定する O(M(M+N))が間に合う。

提出コード

atcoder.jp

ABC191 C - Digital Graffiti

atcoder.jp

感想 (解答中に考えたこと)

  1. 難読では……？ ちょっと調べてみて納得したが、もう少しサンプルほしい……。
  2. 辺の向きのベクトル(辺の方向と垂直な向き)が変わるたびにカウントするも、サンプルすら合わない。
  3. 解説ACした。辺が生じるときは角が必ず存在するので、zip(range(H-1), range(W-1))の範囲で 2\times 2で角かどうか (つまり黒または白のマスが1つだけ)を判定し、その数を出力すれば良い。難しいが、思いつけるようになりたい……。

提出コード

atcoder.jp

ABC166 E - This Message Will Self-Destruct in 5s

atcoder.jp

感想 (解答中に考えたこと)

  1. |i-j|=A_{i} + A_{j}の組を見つける問題。前提として O(N^2)は無理。 iと jに分けると、 i - A_{i} = j + A_{j} \; (i > j), i + A_{i} = j - A_{j} \; (j > i)
  2. また組の数が分かれば良いので、 i > jのような条件に固定しても問題ない。
  3. 以上のことから、 i + A_{i}をkeyにHashMapにその個数を保存し、 i - A_{i}\; (i = 1, 2, 3, ... N)で検索して個数の和を出力すれば良い。

提出コード

atcoder.jp

ABC194 D - Journey

atcoder.jp

感想 (解答中に考えたこと)

  1. 漸化式をそのまま実装すればできるのでは…？つまり N個の頂点があって n個目の頂点をつなげる期待値を E(N, n)として、 E(N, n+1) = E(N, n) + \frac{N-n}{n}\sum^{\infty}_{i=1}\left(\frac{n}{N}\right)^{i}i = E(N, n) + \frac{N}{N-n}
  2. 開始位置と終わりの位置に気をつけて実装する。

提出コード

atcoder.jp

CodeFestival 2016 qual A C - Next letter

atcoder.jp

感想 (解答中に考えたこと)

  1. 前から貪欲にaに変えていけば良い。変えられない場合は嬉しくない変形になるのでスルーし、次の文字の変形にトライする。
  2. 最後の文字の場合はKになるまで操作を行えば良い。(それ以外の文字で操作すると嬉しくない)

提出コード

なんかめっっっっちゃバグらせた

atcoder.jp

緑diff精進 その1 (1/23)

近況報告

レート4桁になった。 atcoder.jp

ところで最近悲しいくらい精進できていない。就活や研究が若干忙しいせいもあるが、普通に怠惰。

AtcoderProblems Heatmap
ということで水コーダー目指してAtCoder ProblemsのRecommendation (Moderate)を埋めていく日記をつけていくことにする。

あくまで日記なので、解説ではないことに注意してほしい。

あと大嘘担当大臣していたらひっそりと教えてください。

本編 (解いた問題)

  • ABC253 E - Distance Sequence
  • ABC140 D - Face Produces Unhappiness
  • ABC223 D - Restricted Permutation

ABC253 E - Distance Sequence

atcoder.jp

感想 (解答中に考えたこと)

  1. i番目の要素が決まれば i+1番目の要素の候補がわかるので、DPで解けそう (制約的にもDPっぽい)
  2. i番目の要素は必ず保持しなければならないので、 dp(i, m):= i番目の要素の大きさがmであるような数列の数

  3. 遷移を考える。 i番目の要素が mである時、 i-1番目の要素は m-K以下か m+K以上であるので

    • dp(i, m)=\sum_{j=1}^{m-K}dp(i-1, j) + \sum_{j=m+K}^{M}dp(i-1,j)

  4. 1番目の要素は何を選んでも良いので、 dp(0, m)=1

  5. 計算量が O(NM^2)だが、累積和で O(NM)で解ける
  6. 実装するもバグる。ランダムテスト(N, M, K) = (2, 2, 0)の場合に答えがズレている
  7. 3.の式でK=0のとき、 dp(i-1, m)を2回計上しているので、上記の式のままだと面倒な分岐が必要そう
  8. 差を取る方針に変更する
    • dp(i, m)=\sum_{j=1}^{M}dp(i-1, j) - \sum_{j=m-K+1}^{m+K-1}dp(i-1,j)

提出コード

atcoder.jp

ABC140 D - Face Produces Unhappiness

atcoder.jp

感想 (解答中に考えたこと)

  1. ランレングス圧縮っぽい。とりあえず幸福な人数はsum(c-1 for _, c in T)であることはわかる。
    • ランレングス圧縮後の文字列を T=L_{a}R_{b}L_{c}R_{d}...とした。
  2. 操作前後の評価を慎重に確認してみる。どんなに最適なムーブをしても最大で2ずつしか増えない。
  3. Tについて、 L_{i}R_{j}といった取り方や端を選択してしまうと嬉しくない。
    • というよりも、 Lや Rの単一のまとまり かつ 端でないような取り方をするのが一番嬉しいムーブになる。
  4. つまり Tで先頭から順に見た時、末尾でなく先頭の文字と異なる文字が現れる回数が K以下であれば はじめの幸福な人数 + K \times 2、そうでなければ全て同じ方向を向けるので N-1になる
    • 前半の条件がわかりにくい。 T = L_{2}R_{3}L_{1}R_{5}L_{3}R_{1}である場合、先頭の文字が Lなので、異なる文字は3回( R_{3}, R_{5}, R_{1})現れ、うち R_{1}は末尾なので、末尾でなく先頭の文字と異なる文字が現れる回数は2回と言える。

提出コード

atcoder.jp

ABC223 D - Restricted Permutation

atcoder.jp

感想 (解答中に考えたこと)

  1. トポロジカルソートっぽい雰囲気。入次数が0の頂点のうち小さい順に要素を選べば良さそう。
  2. priority_queueでも実装可能っぽいけど、MultiSet(SortedSet 厳密には違うもののはず?)の練習がてら後者で実装する。
  3. SortedSetの中身がなくなるまで最小の要素をappendする。appendした頂点は食べたものとして扱えば、いずれ入次数が0になる頂点が現れるので、その都度SortedSetにaddしていく。
  4. SortedSet遅いんですが…… SortedListに変更して、HashSetで数字を利用したかを管理する。

提出コード

atcoder.jp

Rustで競プロがしたい（その１）

前回までのあらすじ

環境構築して、Rustが着丼した。まずはHelloWorldから……ポポーイ！！！！！！！！

azulene-c10h8.hatenablog.com

今回は基本的な構文を確認して、何問かA問題を提出したい。

おためし

fn main() {
    let a = 10;
    let mut b = 11;
    println!("uhoho {}", a);
    println!("uhouho {}", b);
    b += 5;
    println!("hohoho {}", b);
}

PythonというよりかはScalaに近いなぁという印象。 letがimmutableなのはいいね。ただprintln!なのが良く言えば新鮮。

fn main() {
    let x: i64 = 0;
    {
        let x = x + 10;
        println!("x: {}", x); // 10
    }
    println!("x: {}", x); // 0
}

はえ～～～おもしろい。シャドーイングっていうらしい。 let mutっぽい挙動だけど、内部的には新しい変数を作っているのね。

fn main() {
    let test: u32 = "123".parse().unwrap();
    println!("{}", test)
}

parse()の戻り値はResultっていうScalaで言うところのOptionみたいなやつ。 getはunwrapっていうメソッド、getOrElseはunwrap_orっていうメソッドでやる。

(というかrustはsnake caseなのか)

型は色々あるけれど、i(num)とu(num)があって、uはunsignedって意味みたい。JVM系の言語じゃ見かけないと思うけど、Kotlinとかにはあるのか？

fn main() {
    println!("{}", 1 / 2); // 1
    println!("{}", 1.0 / 2); // err!
    println!("{}", 1.0 / 2.0); // 0.5
}

これは意外だ。intをfloatに暗黙に変換してくれるもんだと思っていたけど、演算の際は同じ型じゃないと怒られるみたい。

fn main() {
    let a: [i32; 10] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    println!("{}", a); // err!
    println!("{:?}", a); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    println!("{}", a.map(|v| v.to_string()).join(" ")); // 1 2 3 4 5 6 7 8 9 10
}

Scalaだと無名関数(であってるっけ)はv => v.toString()みたいな書き方をするが、Rustは|v| v.to_string()と書く。なるほどね。

fn main() {
    let a: Vec<i32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    println!("{:?}", a); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    println!("{}", a.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(" ")); // 1 2 3 4 5 6 7 8 9 10
}

なんだこれ！？まぁjoinが使える条件は(おそらく)Stringの配列関連で、collectの際に型を明示的に指定する必要があるっぽい。しかも型パラメータの指定がhoge[T]とかhogeではなくて、hoge::らしい。

他ifやらfor/whileやらを使ってみたけど、これらはpythonっぽい。while Trueじゃなくてloopっていう制御文があるのはびっくりしたが。

その他

Atcoderのジャッジで使えるライブラリは全部突っ込むことにした。Cargo.tomlのdependenciesに以下を突っ込むだけ。

ac-library-rs = "0.1.1"
once_cell = "1.18.0"
static_assertions = "1.1.0"
varisat = "0.2.2"
memoise = "0.3.2"
argio = "0.2.0"
bitvec = "1.0.1"
counter = "0.5.7"
hashbag = "0.1.11"
pathfinding = "4.3.0"
recur-fn = "2.2.0"
indexing = "0.4.1"
amplify = "3.14.2"
amplify_derive = "2.11.3"
amplify_num = "0.4.1"
easy-ext = "1.0.1"
multimap = "0.9.0"
btreemultimap = "0.1.1"
bstr = "1.6.0"
az = "1.2.1"
glidesort = "0.1.2"
tap = "1.0.1"
omniswap = "0.1.0"
multiversion = "0.7.2"
num = "0.4.1"
num-bigint = "0.4.3"
num-complex = "0.4.3"
num-integer = "0.1.45"
num-iter = "0.1.43"
num-rational = "0.4.1"
num-traits = "0.2.15"
num-derive = "0.4.0"
ndarray = "0.15.6"
nalgebra = "0.32.3"
alga = "0.9.3"
libm = "0.2.7"
rand = "0.8.5"
getrandom = "0.2.10"
rand_chacha = "0.3.1"
rand_core = "0.6.4"
rand_hc = "0.3.2"
rand_pcg = "0.3.1"
rand_distr = "0.4.3"
petgraph = "0.6.3"
indexmap = "2.0.0"
regex = "1.9.1"
lazy_static = "1.4.0"
ordered-float = "3.7.0"
ascii = "1.1.0"
permutohedron = "0.2.4"
superslice = "1.0.0"
itertools = "0.11.0"
itertools-num = "0.1.3"
maplit = "1.0.2"
either = "1.8.1"
im-rc = "15.1.0"
fixedbitset = "0.4.2"
bitset-fixed = "0.1.0"
proconio = "0.4.5"
text_io = "0.1.12"
rustc-hash = "1.1.0"
smallvec = "1.11.0"

実践編

ABC334A

単なるif文の確認。inputにproconioっていうマクロ？を使わなきゃいけないっぽい。 でもinput楽チンでいいね。

atcoder.jp

ABC333A

for文と出力の調整。vectorを文字列に変換する操作、もう少しスマートにできないかなぁ。

atcoder.jp

ABC333B

文字コードの差分を計算するのが一番楽。Stringやらstrやらそれらのポインタやらややこしいね～～～～。 特にs.to_string().as_str()がうまく行かないのはびっくりした。s.to_string()が一時的な変数で、as_str()が来ると即座にリリースされてしまうかららしい？ s.to_string()を変数に束縛してやることが必要っぽい。

atcoder.jp

感想

めちゃくちゃ型安全な言語だな～～～って印象。PythonよりかはScalaやKotlin的なBetterJavaって感じの文法で、メモリについては大変気をつけなきゃいけない。

あとはオーバーフローとかを気をつけながら実装する必要があるかな。これまでのABCのAB(C)問題くらいまでRustで解き直して、良い書き方とかを見つけたい。