この記事は IQ1アドベントカレンダー2019 の 5日目の記事です。
今回はちょっとした小ネタ記事として、splay treeのvisualizationを簡易的に作った話を書きます。
続きを読むCodeChef October Challenge 2019: Faulty System
CodeChef October Challenge 2019の問題: Faulty System (Code: CNNCT2)
問題ページ: Contest Page | CodeChef
色々考えたけど、コンテスト中に解けなかった問題。
ずっと悩んでMatroid Intersectionを知らない人をした。
問題概要
頂点と
個の無向辺が含まれる２つのグラフが与えられる。
2つのグラフの各頂点にはから
、各辺には
から
の番号がついている。
2つのグラフについて、同じ番号の辺を用いて両方を連結グラフにしたい。
連結グラフにするために必要な最小辺数はいくらか？
CodeChef October Challenge 2019: Fun with Lists
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
CodeChef October Challenge 2019の問題: Bacterial Reproduction (Code: BACREP)
問題ページ: Contest Page | CodeChef
問題概要
根頂点が頂点1の根付き木がある。
はじめ、各頂点に細菌が存在し、頂点には
匹存在する。
各秒において、以下が発生する。
- 葉でない各頂点
について、子頂点の数を
とする。その頂点に存在する細菌を
匹とした時、
匹に分離した上で各子頂点に
- ある1頂点に細菌が何匹か出現することがある
秒目から
秒目 の
秒間の各秒に対し、以下のクエリを処理せよ
- '+ v k': この秒の間に頂点
匹の細菌が出現する (ただしこの秒数では分裂移動しない)
- '? v': この秒で細菌が分離し移動した時点での頂点
CodeChef October Challenge 2019: Queries on Matrix
CodeChef October Challenge 2019 の問題: Queries on Matrix (Code: JIIT)
問題概要
の行列が与えられる。全ての要素は初め 0 である。
行目
列目の要素を
として記述する。
以下の操作をちょうど 回行う。
- 1つの要素
を選ぶ
列目の全ての要素に 1 を足す
回の操作の後、行列全体の内で要素が奇数となる要素の数を
個とする要素の操作列は何通り存在するかを modulo 998244353 で求めよ。
(操作列は、異なる順序で要素を選ぶもの同士を区別する)
LCAをベースに構築するAuxiliary Treeのメモ
(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 だったらしい。
以下を参考にしている。
- 虚树学习笔记 - Sengxian's Blog
- 競技プログラミングにおけるLCA問題まとめ [auxiliary tree] - はまやんはまやんはまやん
- ICL1705 - Editorial - editorial - CodeChef Discuss
グラフのchain decompositionで橋と関節点を求める
グラフの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.
