はじめに この記事では AtCoder Beginner Contest 215 D 問題 Coprime 2 を解く、計算量が悪いが AC する解法について書きます。 計算量の良い解法については公式解説を参照してください。 問題 長さ $N$ の正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えら…
はじめに WEB+DB PRESS Vol.122 の特集『Rustで実装！ 作って学ぶRDBMSのしくみ』を読みました。 この特集は、出版社のサイトにも説明があるように、(実際の RDBMS に比べて) わずかな機能のみをサポートする小さな RDBMS を作りあげることで RDBMS の仕組み…
はじめに Chapter 1: Compilers & Virtual Machines Chapter 2: Hello Bytecode! Chapter 3: Compiling Expressions Chapter 4: Conditionals Chapter 5: Keeping Track of Names Chapter 6: String, Array and Hash Chapter 7: Functions Chapter 8: Built-…
はじめに 親の親の親の…… 木の入力形式によってはバグに気づけない はじめに ダブリングで LCA を求めるスニペットがバグっていました。Library Checker で AC したので大丈夫かと思っていたのです。 バグに気づけなかった理由は木の入力形式だとわかりまし…
はじめに FParsec 結果 数値の parse 空白の parse 文字列の parse 足し算の parse 足し算の parse (複数回) 実行手順 はじめに この問題 を FParsec で解いたので使い方をメモ。 問題概要としては 1 plus 2 plus 3 plus 4 のような入力から 10 を得たい、と…
まえがき 隣接マスを走査するライブラリ まえがき 競技プログラミングで、グリッドグラフが与えられて、隣接 4 マスに移動できる設定はよくあります。 そのときは以下のようなプログラムを書くことになると思います。くわしくはこの問題 https://atcoder.jp/…
問題: D - Powerful Discount Tickets 問題概要 解法 証明 ($\star$) の証明 類題 問題概要 $N$ 個の商品の値段 $A_1, A_2, \dots, A_N$ と割引券の枚数 $ M $ が与えられる。$a$ 円の商品に $b$ 枚割引券を使うと $\lfloor a / 2^b \rfloor$ 円で買える。$N…
グラフの話です。 簡単のために、グラフは連結で、多重辺や自己ループがないものとします。 用語の説明 2 色で塗り分けられるとは、次の条件を満たすようにグラフの頂点を 2 色で塗る方法が存在することをいいます。 条件：u と v が辺でつながっている ⇒ u …
はじめに 結論 Cloud Functions Cloud Functions + Cloud Pub/Sub はじめに Slash Command は Slack の機能のひとつです。デフォルトでは /remind や /invite などがあります。 このようなスラッシュ / から始まるコマンドは自作することもできます。たとえ…
石の個数が同じになってはいけないニムはマヤゲームと呼ばれます。(参考: 『石取りゲームの数学～ゲームと代数の不思議な関係～』) 正確には、マヤゲームとは 通常のニムで指せる手のうち、ある $2$ 山の石が同じ個数になる手はダメ それ以外は OK 指せる手…
ニム和とニム積に関して分配法則が成り立ちます。 『石取りゲームの数学～ゲームと代数の不思議な関係～』(佐藤文広) にある証明とまったく同じです。それを補足しながら説明します。 非負整数全体 ($0$ 以上の整数全体) を $\mathbb{N}_0$ と書きます。 定…
CodeChef March Challenge 2019 - Cheating on Queue の解説です。列に割り込みで入ってもおこられない最前の位置を求める問題です。Time Limit がきびしいです。
NimKの必勝判定・必勝側の具体的な手の選択について書きます。 後者は前者の証明に出てくるのですが念のために?指す手を求めるプログラムを書きました。
木の中心が直径上に存在すること 中心を見つけるアルゴリズム について書きます。 木の中心とは「各頂点への距離の最大値」が最小になる頂点 (の集合) です。 頂点 $v$ から各頂点への距離の最大値を $ E(v) $ と書きます。つまり、 $$ E(v) = \max_u\{\math…
テキスト文字列 txt にパターン文字列 pat が現れる位置を求めます。 たとえば txt = "abaaaba", pat = "aab" のとき、テキストの $4$ 文字目からパターンが現れます。 abaaaba aab 素朴な方法として、パターンの開始位置を全通り試すというものがあります。…
ラジオNIKKEI第2では平日の08:00-23:00にずっと音楽が流れています。 www.radionikkei.jp OA曲は ここ から見れます。 radikoを起動して選曲をするまでは声だけでできるけど、曲名を知りたいときにスマホを使わないといけないのはつらかったのでスキルを作り…
まとめ A, Bの2完 アナウンスの人の声が良い ケーキが美味しい はじめに 予選で272位 & 20卒だったので本戦に行きました。20卒枠は交通費も出るのでうれしいです。 起床 成功です。 DDCC始発部の朝は早い。— ikd (@ia7ck) 2019年1月18日 到着 受付 受付は ア…
パソコンを使ったのでたぶんAIです。 youtu.be github.com AI ver.1 ランダム ver.2 評価関数 ver.3 GA 思い出 AI ver.1 ランダム ピースをランダムに回転させてランダムな位置に落とします。すぐにゲームオーバーになります。 ver.2 評価関数 各ターンでピ…
micro editor で Insert Line Above/Below するプラグインを作りました。 VSCode で Ctrl+Enter とか Ctrl+Shift+Enter とかに割り当てられている *1 あれです。 レポジトリ Demo コード インストール 使い方 キーボードショートカット メモ マクロじゃダメ…
ABC108/ARC102 D 公式解説の英語版の方法 $L=L'$のグラフから$L=L'+1, 2L'$のグラフを作るには $L=L'+1$ 先頭から末尾の頂点へ長さ$L'$の辺を引く $L=2L'$ すでに引いてある辺の長さを全て2倍にして、末尾の頂点から新しい頂点へ長さ$0$と長さ$1$の辺を引く
二分ヒープを実装しました。 機能 操作 最悪計算量 最大（最小）値の取得 $O(1)$ 要素の挿入 $O(\log_2 n)$ 最大（最小）値を持つ要素の削除 $O(\log_2 n)$ $n$はヒープの要素数です。 実装 up-heapは簡単だけど、down-heapは子が2つある場合優先度の高いほ…
数独（SUDOKU)をプログラム (Ruby) で解きます。 アルゴリズム マスを前から見ていって、空欄のマスに1, 2, ..., 9の順で置けるかどうか試します。 置けるならその数字を置いて次のマスを見る どの数字も置けないなら、いままでの数字の置き方がまずかったと…
はじめに 数式が入力できるチャットを作りました → matcha 想定している活用法は (La)TeXの練習として 数式を含むかんたんな議論の場として などです。 Demo 数式入力 機能 数式のライブプレビュー 入力した内容がすぐに数式に変換されるため、文法エラーな…
はじめに バンドリ！ ガールズバンドパーティ！ いいですよね。 キャラクターの間での呼称が気になったときどうしましょうか。ペアをバンドに含ませてライブをしてかけあいのセリフが出るのを待つ・図鑑でタップ連打・ストーリーを読み直す などがありますが…
はじめに ACM-ICPC 2018 Asia Yokohama Regionalにチーム super_ikd で参加しました。結果はABCの3完103位でした。 チーム チーム名：super_ikd メンバー niyarin さん 研究が忙しそう！ srup さん 問題の解法検索したらブログがよくヒットする！ ikd （自分…
はじめに Demo 説明 機能 構成 サーバサイド フロントエンド インフラ おわりに はじめに yukicoderでは隔週くらいで金曜にコンテストが開かれています。 毎回のコンテストでの自分の成績が一覧できると便利です。 yukicon-historyを使うと、各コンテストで…
https://ia7ck.github.io/visualization/sqrt-decomposition/ Square Root Decomposition のアニメーション 平方分割について：セグメント木をあきらめた人のための平方分割 - くじらにっき++ 上のアニメーションはこの記事のRUQ (Range Update Query) ；色…
難易度7を埋めました。→ AOJ/AtCoder-JOI 埋めたといいつつ、100%ではないです。（1つは提出してもIEになるので） 感想など → https://comprolog.netlify.com/categories/joi/
問題 HACK TO THE FUTURE 2018予選 - AtCoder 本番の解答 9891030405点 Submission #2104678 - HACK TO THE FUTURE 2018予選 本番の後、この記事（競プロ解法紹介～レベル別マラソンの戦い方～）を参考にして解き直したら9990441025点になりました*1 左：989…
問題 格子点2点を結ぶ線分上にある格子点は（端点を含めて）いくつありますか 答え $gcd(|x_1-x_2|, |y_1-y_2|)+1$ 個です 原点(0, 0)と(a, b)を結ぶ線分を考えていいでしょう（a≧0, b≧0, a,bは整数） もとの問題はむずかしすぎるので、解ける問題を解きます…
