日々drdrする人のメモ

今日も明日もdrdr

Splay Treeの可視化Webページを簡易的に作った

この記事は IQ1アドベントカレンダー2019 の 5日目の記事です。adventar.org今回はちょっとした小ネタ記事として、splay treeのvisualizationを簡易的に作った話を書きます。

CodeChef October Challenge 2019: Faulty System

CodeChef October Challenge 2019の問題: Faulty System (Code: CNNCT2) 問題ページ: Contest Page | CodeChef色々考えたけど、コンテスト中に解けなかった問題。 ずっと悩んでMatroid Intersectionを知らない人をした。 問題概要 頂点と個の無向辺が含まれ…

CodeChef October Challenge 2019: Fun with Lists

CodeChef October Challenge 2019の問題: Fun with Lists (Code: TANDON) この問題は、他からのコピーだったという理由より問題が気づいたら消えてた。They removed TANDON! - CodeChef Discuss Forumによれば、以下の問題と同じらしい。 Reverse | Matrix E…

CodeChef October Challenge 2019: Bacterial Reproduction

CodeChef October Challenge 2019の問題: Bacterial Reproduction (Code: BACREP)問題ページ: Contest Page | CodeChef 問題概要 根頂点が頂点1の根付き木がある。はじめ、各頂点に細菌が存在し、頂点には匹存在する。各秒において、以下が発生する。 葉でな…

CodeChef October Challenge 2019: Queries on Matrix

CodeChef October Challenge 2019 の問題: Queries on Matrix (Code: JIIT)Contest Page | CodeChef 問題概要 の行列が与えられる。全ての要素は初め 0 である。行目列目の要素を として記述する。以下の操作をちょうど 回行う。 1つの要素 を選ぶ 行目の全…

LCAをベースに構築するAuxiliary Treeのメモ

(2019/09/15 20:50頃追記) ただAuxiliary Treeと書くと(一般的すぎて)齟齬を生む可能性が高いので、タイトル及び一部文章を変更しました。申し訳ないです。今回はLCAをベースに構築するAuxiliary Treeについて取り上げてます。最近、LCAを元に構築する Auxil…

グラフのchain decompositionで橋と関節点を求める

グラフのchain decompositionと、それを使って橋と関節点を求める手法のメモ橋と関節点を求める手法といえばlowlinkを用いた手法が存在するが、他の手法としてchain decompositionを用いた手法が存在する。(WikipediaのBridge (graph theory)とBiconnected c…

CodeChef July Challenge 2019: Maximum and Minimum

CodeChef July Challenge 2019 の問題: Maximum and Minimum (Code: MXMN) 問題ページ: Contest Page | CodeChef 問題概要 無向グラフに対して関数 を定義する。 = 頂点から頂点までの全てのパスの内での、パスの重みの最小値 パスの重みは、パスに含まれる…

CodeChef July Challenge 2019: LOVEMUFFIN

CodeChef July Challenge 2019 の問題: LOVEMUFFIN (Code: LVMFFN) 問題ページ: Contest Page | CodeChef 問題概要 1からまで番号が付いた人のメンバーがいる。 このメンバーでドルを分配する。この分配の方法の決め方は から以下のように行う。 番号の人が…

CodeChef July Challenge 2019: Snake and Apple Tree

CodeChef July Challenge 2019 の問題: Snake and Apple Tree (Code: CNKAPT) 問題ページ: Contest Page | CodeChef 問題概要 の二次元盤面があり、各マスは空もしくは壁で構成される。 この盤面には 匹のヘビが存在する。各ヘビは秒間の間、各秒ごとに以下…

CodeChef July Challenge 2019: Hit the Coconuts

CodeChef July Challenge 2019 の問題: Hit the Coconuts (Code: CCC) 問題ページ: Contest Page | CodeChef 問題概要 個のココナッツがあり、番目のココナッツは回叩くと割れる。 しかし、個のココナッツはシャッフルされ、どのココナッツが何回叩けば割れ…

Segment Tree Beatsの実装メモ (Historic Informationまわり)

Segment Tree Beats(SGT Beats)のHistoric Informationまわりについて自分が理解した範囲のメモこの記事は以下の続き。これらの説明を前提に書いてある。

UOJ - #164: V

Historic Informationまわりの勉強で解いた。解法メモuoj.ac 問題概要 の番号がついたタンクがある。番目のタンクには最初mの高さの水が入っている。以下のクエリを合計回処理せよ。 の各タンクの水の高さをm上昇させる の各タンクの水の高さをm減少させる (…

Segment Tree Beatsの実装メモ (応用的な例題まわり)

前回の記事の続き smijake3.hatenablog.comコドフォのSegment Tree Beatsの説明の例題として挙がっているTask 3,4を実装したので、そのあたりの考え方含めて書いておく A simple introduction to "Segment tree beats" - Codeforces

Segment Tree Beatsの実装メモ (基本まわり)

Segment Tree Beats(SGT Beats)の基本的なところの自分の理解をまとめておく。 今回は主に考え方や実装の説明メインで、Historic Informationや計算量解析周りの説明は含まない。(ここらへんも理解できて書けたら書く)

AtCoder: Tenka1 Programmer Contest 2019 - D問題: Three Colors

コンテスト中に解けなかった。だめだめだった。atcoder.jp 問題概要 個の整数が与えられ、番目の数はである。各数について赤、青、緑の3色で塗り分けることを考える。 そして塗り分けた個の数の中で、その色で塗られた整数の総和をそれぞれとする。全ての塗…

AtCoder: Mujin Programming Challenge 2018 - F問題: チーム分け

実際には少なく見積もれる計算量がなかなか慣れない。atcoder.jp 問題概要 人をいくつかのチームに分ける。 この時、番目の人は人以下のチームのみに所属できる。この条件の元、人のチーム分けとして何通り考えられるかをMOD で求めよ。 (ここでは、人は区別…

AtCoder: エクサウィザーズ2019 - E問題: Black or White

コンテスト中に解けなかった問題。思考力が足りなかった (終) 想定解法メモ。atcoder.jp 問題概要 個の黒いチョコレートと個の白いチョコレートがある。黒と白を等確率で選び、選んだ色のチョコレートが存在すれば食べる、をチョコレートがなくなるまで繰り…

AtCoder: エクサウィザーズ2019 - D問題: Modulo Operations

これ解くのに1時間はかかりすぎた。反省回。 atcoder.jp 問題概要 個の整数からなる集合と整数が与えられる。この集合に含まれる1つの整数を取り除き、整数を mod に書き換える。この操作を集合が空になるまでの回行う。集合の整数を取り除く順序は通り存在…

AtCoder Grand Contest 032 - D問題: Rotation Sort

コンテスト中に悩んで解けなかった。想定解法のメモ。 atcoder.jp 問題概要 の順列が与えられる。この順列に対し、以下の操作を行える。 あるを選び、を一つ左にシフトする コストはかかる あるを選び、を一つ右にシフトする コストはかかる を昇順に並べる…

AtCoder: 早稲田大学プログラミングコンテスト2019 - D問題: Choose Your Characters

コンテスト時間中に解いた。解法メモ。atcoder.jp 問題概要 とあるアクションゲームにおいて、の番号が振られた種類のキャラがいる。 これらのキャラには、対戦する際の有利不利、もしくは五分の関係がある。 (キャラがキャラに対し有利である場合は、必ずキ…

AtCoder: AtCoder Grand Contest 028 - B問題: Removing Blocks

組み合わせを計算する問題は、計算の視点がうまく合わせられないとなかなか計算できなくて、頭を抱える...。 結局、公式の解法を見て通した。atcoder.jp 問題概要 個のブロックが一列に並んでいて、番目のブロックの重さはである。このブロックを1つずつ取り…

AtCoder: 全国統一プログラミング王決定戦本戦 - G問題: Greatest Journey

コンテスト中は(E問題でハマってて)見なかった問題。後日公式の解説見ながら通した。atcoder.jp 問題概要 1からNまでの番号が付いた個の頂点を持つ木がある。この木の上を1からMまでの番号がついた人の人が移動し、番目の人は頂点からちょうど回辺を伝って頂…

AtCoder: 全国統一プログラミング王決定戦本戦 - E問題: Erasure

本戦中にはなんとか解けたけど、通り数計算まわりで無限にハマってつらくなった問題。 こんなハマり方はしないようにしたい...。atcoder.jp 問題概要 1からまでの番号付きの個のブロックがある。 を満たすを選び、以上以下のブロックを消すことを考える。こ…

CodeChef February Challenge 2019: Xor Decomposition

CodeChef February Challenge 2019 の問題: Xor Decomposition (Code: XDCOMP) 問題ページ: https://www.codechef.com/FEB19A/problems/XDCOMP 問題概要 1からの番号が付いた頂点の木と一つの整数が与えられる。 グラフの各頂点には重みが付いており、頂点の…

CodeChef February Challenge 2019: Yet Another Tree Problem

CodeChef February Challenge 2019 の問題: Yet Another Tree Problem (Code: TRDST) 問題ページ: https://www.codechef.com/FEB19A/problems/TRDST 問題概要 頂点に1からまでの番号が付いた頂点の木が与えられる。 また、頂点と頂点の距離をとする。が与え…

DPまとめコンテスト - O問題: Matching

問題: O - Matching気づき含めた解法メモ 問題概要 人の男性と人の女性がいる。男性と女性の相性の良し悪しがによって与えられ、1なら相性が良く、0なら相性が悪い。ここで、相性の良い男女同士のペア組を作るとき、これは何通り存在するか。で割った余りで…

CodeChef December Cook-Off 2018: Swag Subsets

CodeChef December Cook-Off 2018 の問題: Swag Subsets (Code: SOSTD) 問題ページ: https://www.codechef.com/COOK101A/problems/SOSTDコンテスト中に無限に実装バグらせて解けなくて、後で解いたやつ。 問題概要 2つの整数の列 と が与えられる。ここで、…

競プロライブラリのページをAsciiDocで作った話

この記事は、"IQ1 Advent Calendar 2018"の13日目の記事です。 adventar.org今回は、自分用の競プロライブラリのWebページを最近AsciiDocで作ったので、この話を書きます。競プロよりもAsciiDocメインの記事です。 tjkendev.github.io

ねむみの社会人1年目とお昼ごはんの振り返り

この記事は、IQ1の2まいめっ Advent Calendar 2018 の10日目の記事です。 adventar.org社会人1年目+お昼ごはんの振り返りっぽい何かを書きます。