naoya_t@hatenablog

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

ゆるふわ競プロオンサイト ＠FORCIA #2 ゴリラの挑戦状

Programming Contest


9/14(土) 13:30-19:00（コンテストは14:10-16:10）
オンサイト参加登録一番乗りしていたのだけれど、都合により当日都内（国内）にいないことが確定してキャンセル
でオンライン参加
9完で8位（オンライン参加2位）
f:id:n4_t:20190929144522j:plain:w600
（※全部で10問だと思ってたら2ページ目があった）

（あとで書く）

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

Algorithms memo

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

内容的には

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

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

続きを読む

A - GAFA文字列

neta memo

A - GAFA文字列

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

問題文

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

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

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 を表示します。

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)でLCP arrayが構築できる方法

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

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

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

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

続きを読む

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:w320f:id:n4_t:20190406115749j:plain:w320
全員予選通過ライン（30点）は超えられたので目的は果たせたかと

会場でD-smallまで解いて（提出は帰宅後）
その後D-largeも解いて終了。

終了後ジャッジでLargeも全て通って100点満点
f:id:n4_t:20190407110603p:plain
次はRound 1でお会いしましょう。

【参考資料】当日のセットリスト（誰がどれを歌ったかは秘匿）
docs.google.com

*1:1AC→1曲歌ったら次の問題に進める

続きを読む