Splay Treeの可視化Webページを簡易的に作った
CodeChef October Challenge 2019: Faulty System
CodeChef October Challenge 2019の問題: Faulty System (Code: CNNCT2)
問題ページ: Contest Page | CodeChef
色々考えたけど、コンテスト中に解けなかった問題。
ずっと悩んでMatroid Intersectionを知らない人をした。
問題概要
頂点と個の無向辺が含まれる2つのグラフが与えられる。
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 を足す
- 列目の全ての要素に 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.