ニム和とニム積に関して分配法則が成り立ちます。 『石取りゲームの数学～ゲームと代数の不思議な関係～』(佐藤文広) にある証明とまったく同じです。それを補足しながら説明します。 非負整数全体 ($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日 到着 受付 受付は ア…