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

Algorithms memo

LeetCode Weekly Contest 146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。

内容的には

マンハッタン距離が最大である2点を選ぶ問題 - ICPC突破専用ザク

を理解する過程で噛み砕いたものなので、上記記事を既読の方は本稿を読むには及ばない。

MathJaxの不具合なのか、 $\max$ の下に $2^{k-1}$ が書けなかったので $2^k/2$ で代用。

2019-07-14

お知らせ

memo

競プロ精進記録は
naoya_t@hatenablog (競プロ精進編)*1
に移しました。

*1:競プロer限定公開

2019-06-05

A - GAFA文字列

neta memo

A - GAFA文字列

実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100点

問題文

Google, Apple, Facebook, Amazon各々の頭文字G,A,F,Aのみからなる文字列をGAFA文字列と呼びます。

GAFA文字列 $s$ が1つ与えられます。高橋君はこの文字列に以下の操作を $K$ 回まで行うことができます。

Appleの頭文字のAを1つAtCoderのAに置き換える
Amazonの頭文字のAを1つAtCoderのAに置き換える

AtCoderの頭文字のAはAtCoderのAに置き換えることができません。

この操作の後にできる文字列の中で、Aが最も多く含まれるものを表示してください。複数ある場合はどれを表示しても構いません。

制約

$s$ は'G','A','F','A'のみからなる文字列
$1\le|s|\le2\times10^5$
$0\le K\le|s|$

入力

入力は以下の形式で標準入力から与えられる。

K
s

出力:

操作の後にできる文字列の中で、Aが最も多く含まれるものを出力せよ。

入力例1

1
GAFA

出力例1

GAFA

Appleの頭文字のA（文字列の2文字目）をAtCoderのAに置き換えたもので、Aが2つ含まれます。

他にも、Amazonの頭文字のA（文字列の4文字目）をAtCoderのAに置き換えた

GAFA

もこの条件にあてはまります。

入力例2

0
GAFA

出力例2

GAFA

文字を置き換えることができないので、入力と同じ GAFA を表示します。

2019-05-13

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

Algorithms memo

suffix arrayは知ってます。（当然）
（知ったきっかけは何だったかな…高林さんのsaryかな）
以前、英辞書検索用のCLIツールを作る時などにも使いました。

でも今までずっと、文字列のポインタを1つずつずらした（文字列の長さ分の）char**配列を用意してqsortでstrcmp的なものを渡すような、愚直な（ $O(N^2\log N)$ の）書き方しかしたことがありませんでした。

あまりそれで困るような場面に遭遇したことがなかったということでもありますが、
競プロで使うとなるとそういうわけにはいきません。

制約が $N=|S|=10^5$ とかだともう無理ですよね。

LCP（最長共通プレフィックス）array もそうです。
suffix arrayを作った後に、隣り合う項目同士の最長共通プレフィックスを求めておくやつです。
隣同士の最長共通プレフィックスのリストがあると、あとはRMQとか使えば任意の2つのサフィックスの共通プレフィックスが求められたりして便利（らしい）です。
（配列の長さ-1）組の文字列の比較なので普通に考えたら $O(N^2)$ かかります…よね*1。

なのに、 $N=10^5$ なのにいかにもsuffix arrayとLCP（最長共通プレフィックス）arrayを計算して下さいと言わんばかりの問題*2が来て、上位陣はsuffix arrayで通しているというのです。

そこで

O(N)でsuffix arrayが構築できる方法

と

O(N)でLCP arrayが構築できる方法

について調べてみました。

上級者の皆様には「そんな事も知らなかったのか」「蟻本（上級編）に書いてあるぞ」「蟻本読め」「蟻本」と思われることでしょうが青コーダーレベルだと今までそれで困る場面がなかったということでお許しください。

*1:蟻本上級編を読めというお叱りはあとで受けます。

*2:毎週日曜開催の某コンテストで最近そんな問題が出ました。

2019-04-07

Google Code Jam 2019 - Qualification Round

Google Code Jam Programming Contest

4/6(土)08:00 - 4/7(日)11:00
Qualに限って相談OKなので、有志4人で集まって電源wifi完備なカラオケルームを借りて参加*1
f:id:n4_t:20190406111753j:plain:w320 f:id:n4_t:20190406115749j:plain:w320
全員予選通過ライン（30点）は超えられたので目的は果たせたかと