naoya_t@hatenablog

いわゆるチラシノウラであります

memo

チェビシェフ距離への置き換えを利用して(k次元)マンハッタン距離の最大値を求める方法

LeetCode Weekly Contest 146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。内容的には マンハッタン距離が最大である2点を選ぶ問題 - ICPC突破専用ザク を理解する過程で噛み砕いたものなので、上記記事を既読の方は本稿を読む…

A - GAFA文字列

A - GAFA文字列 実行時間制限: 2 sec / メモリ制限: 1024 MB 配点: 100点 問題文 Google, Apple, Facebook, Amazon各々の頭文字G,A,F,Aのみからなる文字列をGAFA文字列と呼びます。GAFA文字列 が1つ与えられます。高橋君はこの文字列に以下の操作を回まで行…

Suffix Array(接尾辞配列)とLCP(最長共通接頭辞)arrayを線形時間で構築する方法を調べてみた 〜SA-ISとKasai's algorithm〜

蟻本p.337 "なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。例えば、SA-ISと呼ばれるアルゴリズムなど、線形時間で非常に高速に構成するアルゴリズム等も存在していますが、プログラミングコンテストではほとんどの場合で上のアルゴリ…

〈説明用メモ〉O(3^N)について本気出して考えてみた

個ある何かの0個以上から成る集合をビットの整数で表すことにする。 このとき、集合に含まれる要素が個なら全部でビット立っている 。 (__builtin_popcount(S) == k)この集合の部分集合をすべて列挙しようとすると、空集合も含め通りある。 集合Sとしてあ…

Kindle Oasis(第9世代)を買った話

我が家にKindle Oasis(第9世代)がやってきました。 去年の秋にKindle Paperwhiteを買って以来、Kindle版書籍を積読したり自炊したPDFを消化したりに毎日愛用していましたが、もっと画面が広ければ自炊本でも実用的に読めるのになーと思っていました。

拡張ユークリッド互除法の話

先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)拡張ユークリッド互除法というのは、 を満たす を求める方法。 を で割れば…

連分数 (continued fraction)

連分数 - WipikediaこないだのJune Long ChallengeのEuler Sumを考えてる時に Mark Jason Dominus氏のスライド Arithmetic with Continued Fractions を読んだ時のメモ。連分数とかいじるのって多分昔SICPを読んだ時以来。

小さい数n(100万までとか)の素因数分解

CodeChefのフォーラムで June Challenge 2017の問題 Chef and Prime Queries (PRMQ) の解法を読んでいて discuss.codechef.com素因数分解をするのに This can be done by creating a Smallest Prime Factor array in the sieve function itself. とあって。…