この記事は IQ1アドベントカレンダー2019 の 5日目の記事です。
今回はちょっとした小ネタ記事として、splay treeのvisualizationを簡易的に作った話を書きます。
続きを読むCodeChef October Challenge 2019の問題: Faulty System (Code: CNNCT2)
問題ページ: Contest Page | CodeChef
色々考えたけど、コンテスト中に解けなかった問題。
ずっと悩んでMatroid Intersectionを知らない人をした。
頂点と個の無向辺が含まれる2つのグラフが与えられる。
2つのグラフの各頂点にはから、各辺にはからの番号がついている。
2つのグラフについて、同じ番号の辺を用いて両方を連結グラフにしたい。
連結グラフにするために必要な最小辺数はいくらか?
CodeChef October Challenge 2019の問題: Fun with Lists (Code: TANDON)
この問題は、他からのコピーだったという理由より問題が気づいたら消えてた。
They removed TANDON! - CodeChef Discuss
Forumによれば、以下の問題と同じらしい。
Reverse | Matrix Exponentiation & Math Practice Problems | HackerEarth
とりあえず解いたので書いておく。
整数をとり、その桁を逆順にした整数を返すを定義する。
(, )
桁以下のの倍数の整数のうち、もの倍数になる整数の個数をmodulo で求めよ。
CodeChef October Challenge 2019の問題: Bacterial Reproduction (Code: BACREP)
問題ページ: Contest Page | CodeChef
根頂点が頂点1の根付き木がある。
はじめ、各頂点に細菌が存在し、頂点には匹存在する。
各秒において、以下が発生する。
秒目から秒目 の 秒間の各秒に対し、以下のクエリを処理せよ
CodeChef October Challenge 2019 の問題: Queries on Matrix (Code: JIIT)
の行列が与えられる。全ての要素は初め 0 である。
行目列目の要素を として記述する。
以下の操作をちょうど 回行う。
回の操作の後、行列全体の内で要素が奇数となる要素の数を 個とする要素の操作列は何通り存在するかを modulo 998244353 で求めよ。
(操作列は、異なる順序で要素を選ぶもの同士を区別する)
(2019/09/15 20:50頃追記) ただAuxiliary Treeと書くと(一般的すぎて)齟齬を生む可能性が高いので、タイトル及び一部文章を変更しました。申し訳ないです。今回はLCAをベースに構築するAuxiliary Treeについて取り上げてます。
最近、LCAを元に構築する Auxiliary Tree を使う問題に出会ったので書いた。
CodeChef July Challenge 2019 で以下の問題があった。
自分は Auxiliary Tree を使わず解いたが、想定解法が Binarization of a tree + Centroid Decomposition on Edge + Auxiliary Tree だったらしい。
以下を参考にしている。
グラフのchain decompositionと、それを使って橋と関節点を求める手法のメモ
橋と関節点を求める手法といえばlowlinkを用いた手法が存在するが、他の手法としてchain decompositionを用いた手法が存在する。(WikipediaのBridge (graph theory)とBiconnected componentに載っている)
以下を参考にしている
[1] Schmidt, Jens M. "A simple test on 2-vertex-and 2-edge-connectivity." Information Processing Letters 113.7 (2013): 241-244.