木の中心

木の中心が直径上に存在すること 中心を見つけるアルゴリズム について書きます。 木の中心とは「各頂点への距離の最大値」が最小になる頂点 (の集合) です。 「各頂点への距離の最大値」を $ E(v) $ と書きます。つまり、 $$ E(v) = \max_u\{\mathrm{dist}(…

KMP法

テキスト文字列 txt にパターン文字列 pat が現れる位置を求めます。 たとえば txt = "abaaaba", pat = "aab" のとき、テキストの $4$ 文字目からパターンが現れます。 abaaaba aab 素朴な方法として、パターンの開始位置を全通り試すというものがあります。…

ラジオNIKKEI第2で流れている曲を教えてくれるAlexaスキルを作った

ラジオNIKKEI第2では平日の08:00-23:00にずっと音楽が流れています。 www.radionikkei.jp OA曲は ここ から見れます。 radikoを起動して選曲をするまでは声だけでできるけど、曲名を知りたいときにスマホを使わないといけないのはつらかったのでスキルを作り…

DDCC2019本戦に参加した感想

まとめ A, Bの2完 アナウンスの人の声が良い ケーキが美味しい はじめに 予選で272位 & 20卒だったので本戦に行きました。20卒枠は交通費も出るのでうれしいです。 起床 成功です。 DDCC始発部の朝は早い。— ikd (@ia7ck) 2019年1月18日 到着 受付 受付は ア…

CRT

CRT(と、拡張ユークリッドの互除法) 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita という素晴らしい記事があります。 それでも理解するのに時間がかかったので整理しておきます。 拡張ユークリッドの互除法 CRT スライド中のソースコー…

テトリスのAIを作った

パソコンを使ったのでたぶんAIです。 youtu.be github.com AI ver.1 ランダム ver.2 評価関数 ver.3 GA 思い出 AI ver.1 ランダム ピースをランダムに回転させてランダムな位置に落とします。すぐにゲームオーバーになります。 ver.2 評価関数 各ターンでピ…

カーソル行の直前・直後に空行を挿入する micro の plugin を作った

micro editor で Insert Line Above/Below するプラグインを作りました。 VSCode で Ctrl+Enter とか Ctrl+Shift+Enter とかに割り当てられている *1 あれです。 レポジトリ Demo コード インストール 使い方 キーボードショートカット メモ マクロじゃダメ…

ABC108/ARC102 D All Your Paths are Different Lengths

ABC108/ARC102 D 公式解説の英語版の方法 $L=L'$のグラフから$L=L'+1, 2L'$のグラフを作るには $L=L'+1$ 先頭から末尾の頂点へ長さ$L'$の辺を引く $L=2L'$ すでに引いてある辺の長さを全て2倍にして、末尾の頂点から新しい頂点へ長さ$0$と長さ$1$の辺を引く

Implementation and Visualization Binary Heap

二分ヒープを実装しました。 機能 操作 最悪計算量 最大(最小)値の取得 $O(1)$ 要素の挿入 $O(\log_2 n)$ 最大(最小)値を持つ要素の削除 $O(\log_2 n)$ $n$はヒープの要素数です。 実装 up-heapは簡単だけど、down-heapは子が2つある場合優先度の高いほ…

数独をプログラムで解く

数独(SUDOKU)をプログラム (Ruby) で解きます。 アルゴリズム マスを前から見ていって、空欄のマスに1, 2, ..., 9の順で置けるかどうか試します。 置けるならその数字を置いて次のマスを見る どの数字も置けないなら、いままでの数字の置き方がまずかったと…

数式が入力できるチャット matcha を作った

はじめに 数式が入力できるチャットを作りました → matcha 想定している活用法は (La)TeXの練習として 数式を含むかんたんな議論の場として などです。 Demo 数式入力 機能 数式のライブプレビュー 入力した内容がすぐに数式に変換されるため、文法エラーな…

ガルパの呼称を検索・登録できるサービス gbp-call を作った

はじめに バンドリ! ガールズバンドパーティ! いいですよね。 キャラクターの間での呼称が気になったときどうしましょうか。ペアをバンドに含ませてライブをしてかけあいのセリフが出るのを待つ・図鑑でタップ連打・ストーリーを読み直す などがありますが…

ICPC 2018 国内予選 参加記

はじめに ACM-ICPC 2018 Asia Yokohama Regionalにチーム super_ikd で参加しました。結果はABCの3完103位でした。 チーム チーム名:super_ikd メンバー niyarin さん 研究が忙しそう! srup さん 問題の解法検索したらブログがよくヒットする! ikd (自分…

yukicon-historyを作った

はじめに Demo 説明 機能 構成 サーバサイド フロントエンド インフラ おわりに はじめに yukicoderでは隔週くらいで金曜にコンテストが開かれています。 毎回のコンテストでの自分の成績が一覧できると便利です。 yukicon-historyを使うと、各コンテストで…

平方分割の可視化

https://ia7ck.github.io/visualization/sqrt-decomposition/ Square Root Decomposition のアニメーション 平方分割について:セグメント木をあきらめた人のための平方分割 - くじらにっき++ 上のアニメーションはこの記事のRUQ (Range Update Query) ;色…

難易度7

難易度7を埋めました。→ AOJ/AtCoder-JOI 埋めたといいつつ、100%ではないです。(1つは提出してもIEになるので) 感想など → https://comprolog.netlify.com/categories/joi/

HTTF 2018 qual

問題 HACK TO THE FUTURE 2018予選 - AtCoder 本番の解答 9891030405点 Submission #2104678 - HACK TO THE FUTURE 2018予選 本番の後、この記事(競プロ解法紹介~レベル別マラソンの戦い方~)を参考にして解き直したら9990441025点になりました*1 左:989…

格子点とGCD

問題 格子点2点を結ぶ線分上にある格子点は(端点を含めて)いくつありますか 答え $gcd(|x_1-x_2|, |y_1-y_2|)+1$ 個です 原点(0, 0)と(a, b)を結ぶ線分を考えていいでしょう(a≧0, b≧0, a,bは整数) もとの問題はむずかしすぎるので、解ける問題を解きます…

Myblog

ドットインストールのRuby on Rails 5入門の言うとおりにしてたらできるやつ↓ Myblog

座標変換行列

Z-Algorithm

名前がかっこいい。

難易度6

難易度6を埋めました。→AOJ/AtCoder-JOI 埋めただけなので、復習する必要があります。

ARC 082 F. Sandglass

問題 F: Sandglass - AtCoder Regular Contest 082 | AtCoder

難易度5

JOIの難易度5を埋めました。→ AOJ/AtCoder-JOI 印象に残った問題を挙げます。だいたい解けなかったやつです。

CSAcademy 10 D. Subarray Medians

問題 https://csacademy.com/contest/round-10/task/subarray-medians/

編入受験記

はじめに 受験した大学 筑波大学理工学群数学類 神戸大学理学部数学科 試験内容と感想 筑波大学 神戸大学 使った本 数学 英語 おわりに

ナナシスのEPISODE.3.5を見る

はじめに EPISODE.1.5と2.5はエピソードキーで開放できるんですが、3.5の開放で戸惑ったので記します。 アプリのダウンロードは以下からできます。 Tokyo 7th シスターズ 開発元:Donuts Co. Ltd. 無料 posted with アプリーチ

便利そう(一人でしか使わないけど) paper.dropbox.com 問題に関して 1時間くらい経ってから二分探索を考えたけど、2秒で捨てた。捨てちゃいけなかった。 ※追記 dropboxへのログインを催促されるのでつらい。

continuity

そろそろcauchy列(基本列)の問題が出そうな気がするけど、何も分かってない(まずい)。

和集合

問題 ベクトル空間$V$の部分空間$U, W$がある。もし$U\cup W$が部分空間になるなら、$U\subset W$または$W\subset U$であることを示せ。