naoya_t@hatenablog

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

チェビシェフ距離への置き換えを利用して（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曲歌ったら次の問題に進める

続きを読む

多倍長整数問題はPythonで

yukicoder 過去問 Python

Joeくんが言及してたやつ


yukicoder No.381 名声値を稼ごう Extra

No.381 名声値を稼ごう Extra - yukicoder

言語の特性上C++,Java,C#で正答するのは困難かもしれません。Ruby,Pythonでの回答をおすすめします。

続きを読む

全国統一プログラミング王決定戦 本戦

AtCoder Programming Contest 過去問

atcoder.jp
主催／日本経済新聞社　共催／AtCoder　協賛／TRI-AD，CISCO
2/17(日) ＠東京ドームホテル 大宴会場「天空」
f:id:n4_t:20190217151752j:plain

予選500位に入ったので決勝大会後のイベント＆懇親パーティーに呼ばれて参加してきました。
f:id:n4_t:20190218181009j:plain
問題文は最初公開されていなかったのだけれど、本戦終盤頃にPDFで公開されたのでKindleに入れてちびちび考えていました。*1

chokudai社長 + PFNの秋葉さん西川さんのトークショーの後、上位３名によるエキシビション（20分8問のコンテスト形式＋chokudai氏の実況）があって凄く面白かったし刺激的でした。
8問全完した準急さんのキー入力はめちゃ速いです。

500人懇親パーティーは美味しい食事＋色々な人と話せて楽しかったです。
f:id:n4_t:20190217194643j:plain:w400
というわけで、本戦＋エキシビションの問題を見ていこうと思います。

*1:本番ではネットワークトラブル回避のため問題文が紙で配られたそうです。

続きを読む

ゆるふわ競プロオンサイト ＠FORCIA

Programming Contest

forcia.connpass.com
2/9(土) 14:00-

FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。
（over28枠に空きが1つ出たのを知って前日に登録）
最初404が出てコンテストがなかなか始められず（CTF？）、HackerRankでコンテスト開催経験のある人が呼ばれて対応に当たっていた…
そして15分遅れて（URLを変更して）コンテスト開始。
100-200-300-400-500-600-700-800 という配点と問題の体感難易度が大きくずれていた気がする。
4完(+部分点)で27位とかそのくらい。
Programming Problems and Competitions :: HackerRank

コンテストだけ出て懇親会は（ピザonlyであることが知られているので）帰るつもりだったけど、皆さんと色々話してて結局懇親会の最後（19:00）まで滞在。（お菓子と飲み物があって助かった）
FORCIAさん@matsu7874さんどうもありがとうございました。

続きを読む