2018-04-22

2018年の抱負（改２）

3月に妻が急病になり、ER搬送からの一週間入院という出来事があった（現在はもう問題なし）。それがきっかけで、自身の健康・キャリアついて色々考え直したので、今年の抱負も合わせて更新しておく。

2018年の抱負

一日7時間睡眠
必須科目。どんなに忙しくても6.5時間は寝る。健康は本当に大事

年収~~+15%~~ → +10%
無理しない額に下方修正。睡眠を削ってまで達成しようとしないこと。
糸井重里さんの『ちゃんとメシ食って、風呂入って、寝てる人にはかなわない』を座右の銘とする。
dot.asahi.com

プロコン再開
もともと今年は控えるつもりだったが、熟考の末、日常的な趣味に戻すことにした。理由は
・プロコンをしないと、仕事のプログラミングを家でやってしまうことがわかった。。。
・アルゴリズムが自分の強みらしいとわかった。自分程度でも田舎の普通のプログラマの中だと突出する
・プロコンがないと、トップレベルのコーダーと絡む機会がゼロになることに気づいた
・ABC/ARCへの定期参加にメドがついた
などなど。

2018-03-04

2018年の抱負（改）

2018年が2か月ほど過ぎたところで、今年の抱負を修正することにした。
まあ端的には、「ちゃんと寝る」と「年収増やす」が重すぎて、趣味にとても手が回らいことが判明しただけ。

2018年の抱負
一日7時間睡眠
強化科目。今のところ達成率が6割程度なので、せめて8割まで上げることにする。忙しい日も6時間は寝よう。

年収+15%
3月に昇給したので残り12%くらい。年末の定期昇給が去年と同じ8%と推定するなら、あと2回くらい特別昇給が必要な計算だ。

低レイヤ分野でレジュメにかけるレベルのアウトプットを何か
具体的には30日OS本と熱血アセンブラ本
これは上２つに比べると趣味的要素が強すぎるため、抱負からは外すことにした。

2018-01-22

HackerEarth December Circuits '17 参加日記

2017年最後のプロコン。57位/5713人で風邪を引いていた割には悪くない。長期型プロコンだと、二桁順位がたまに取れるくらいの実力にはなったようだ。

Two Arrays

同じ長さnの整数列X, Yについて、マッチング数を以下のように定義する。
・X[i] = Y[j], (1 <= i, j <= n)となるインデックス(i, j)のペアの数
整数Kと、長さNの整数列A、および長さMの整数列Bが与えられる。AとBから同じ長さの部分列を抜き出し、マッチング数がK以上になるパターン数を答えよ。
1 <= N, M <= 2000
1 <= A[i] <= 1000000000
1 <= B[i] <= 1000000000
1 <= K <= NM

次のような二次元配列を用意する。
table[i, j] = A[i] とB[j]が等しいなら1、それ以外なら0
すると、table[,]の正方形(i, j)～(k, l)は、A[i, k]とB[j, l]でマッチする組み合わせに等しくなる(1の部分がマッチするところ)。
よって、すべてのi,jの組み合わせについて、(i, j)を左上とした正方形をどんどん大きくしていって、中の1の数がK以上になったところから、限界までの正方形の数を足したものが答えとなる。これは累積和と二分探索で効率よく求めることができる。
https://www.hackerearth.com/submission/13789952/

Left or Right

国Xには、0からN-1で番号付けされるN個の都市があり、サイクルのようにつながれている(都市iは、都市(i + 1)%Nと都市(i - 1 + N)%Nとつながっている）。また、各都市にはタイプA[i]がある。次のQ個のクエリに答えよ。
タイプ１：都市YからタイプZの都市まで、左回りで移動したときの最小ステップ数
タイプ２：都市YからタイプZの都市まで、右回りで移動したときの最小ステップ数
たどり着けないときは-1を返すこと。
1 <= N <= 3000
1 <= Q <= 500000
0 <= Y < N
1 <= A[i], Z <= 200000

都市のタイプごとに、位置をリストでもてばよい。それぞれYの位置をLowerBound()で求め、その次または前のIndexとの差分を返す。
https://www.hackerearth.com/submission/13790214/

HP and Splitting of Array

数列Aについて、A[i] > A[j]かつi < jなら、そのペアはinversionである。すべてのinversionであるペアの合計をinversion countと呼ぶ。長さNの整数列Aが与えれたとき、Aを左にiだけローテーションしたときのinversion countを求めよ。iは1からNのすべての数である。
1 <= N <= 100000
1 <= A[i] <= 1000000
Aに重複する要素はない

ある状態Aのinversion countがすでに求められていたとする。Aを左に1つローテーションしたもののinversion countは、
現在の値 - (A[0]の順位 - 1) + (N + A[0]の順位)
となる(『A[0]の順位』はAを昇順ソートしたときの要素A[0]の位置）。
あとは、初期状態のinversion countを求めれば良い。これはBITを使って効率よく求められる。
https://www.hackerearth.com/submission/13828080/

Berland Programming Contests

N個の都市があり、それらをつなぐ道は全体でツリーを構成している。M種類のコンテストが各都市で開催される（１つのコンテストが複数の都市で開催されうる。ある都市では、あるコンテストが開催されないこともある）。ここで、
・連結したサブグラフを選び
・選んだサブセットで開催されるすべてのコンテストタイプに出場する
とする。この時、コンテストタイプの種類数kだけパスを購入しなければならない。
すべてのサブセットについてこのルールを適応したとき、パス数に対するサブセットの数を、すべてのkについて答えよ。
1 <= N <= 5000
1 <= M <= 10

解けそうで解けなかった問題。
dp[i, j] := 根をiとする木で、状態jになるサブグラフ数
と定義する。初期値を
dp[i, (開催されるコンテストマスク)] = 1
として、葉以外のノードについて、
$dp[i, j] = dp[i, j] + \sum_{k\&l=j}^{} dp[i, k] * dp[x, l] \: (xはノードiの直接の子)$
のようにマージしていけば求められる。
計算は次のテクニックを使ってスピードアップできるらしい。
http://codeforces.com/blog/entry/45223（整数列のすべてのサブセットに対して、その合計を効率的に求める方法）

Buggy Bot

ノード数nの有向グラフ上を、Botがk個のインストラクションにそって移動する。インストラクションは、「現在地がノードxならノードyに移動せよ」というものであり、始めBotはノード1にある。ただし、移動中1回のみ、ランダムに隣のノードへBotが移動してしまうことがある。これは、インストラクションの前後いずれでも起こり得る（1度も起こらないこともある）。
このとき、最終到達地点としてありえるノードを答えよ。
1 <= n <= 100000
1 <= m, k <= 100000

本番ではDFS+メモ化で部分点だった。
ランダム変化がない場合の、ステップごとの位置を最初に算出する。そして、「現在のステップで最終的に到達する場所」をノードごとに保持しながら、うしろから処理していく。
（実装は省略）

2018-01-04

2017年振り返りと2018年の抱負

2017の抱負と結果

~~SRMで黄になる~~ → LongContestで二桁安定 (30%)

Topcoderがアレなので途中で変更した抱負。二桁順位は30%くらいの確率なので達成率も30%。

熱で寝込まない (100%)

風邪は引いても寝込んではいない。すばらしい成果。

ちゃんと寝る (20%)

連続で5時間睡眠を何度かやってしまった。

2018年の抱負

一日7時間睡眠

いいかげん睡眠不足になっていい歳じゃない

年収+15%

去年は+8％だったのでかなりアグレッシブ

低レイヤ分野でレジュメにかけるレベルのアウトプットを何か

具体的には30日OS本と熱血アセンブラ本

プロコンはちょっと控えめにする予定。

2017-11-23

HackerRank Week of Code 35 参加日記

1044位/9458人の酷い結果。以下、易問は省略。

3D Surface Area

HxWの平面上の各セル上に、立方体がいくつか積み重なっている。外部に面している面積を求めよ。

X面からみた面積、Y面からみた面積、Z面からみた面積をそれぞれ求めて足せば良い。
https://www.hackerrank.com/contests/w35/challenges/3d-surface-area/submissions/code/1304126485

Matrix Land

n行m列のマトリックスがあり、各セルには点数が設定されている。1行目の任意のセルから、n行目の任意のセルまで移動したとき、得られる合計得点の最大値を求めよ。ただし、セルの点数は通過後にゼロになる。また、セルからの移動は左右と下のみ可能である。
1 <= n x m <= 4 * 10^6

3日考えて解けなかったDPの問題。これは悔しい。
移動制約により、ある点に到着するルートは2通りしかない。
f:id:yambe2002:20171122071240p:plain
パターン１：ある点より左いずれかに降りてきて、点を通過して右から戻ってくる（通過しない場合も含む）
パターン２：ある点より右いずれかに降りてきて、点を通過して左から戻ってくる（通過しない場合も含む）
パターン１だけ考えてみる。
f:id:yambe2002:20171122071615p:plain
上の矢印で表されるのは、「その行だけを考えたときの、(x, y)より右の合計最大値」であり、
msr[x, y] = Max(msr[x, y + 1] + A[x, y], 0)
と表すことができる。
f:id:yambe2002:20171122071605p:plain
上の矢印で表される部分をmslit[x, y]と定義すると
mslit[x, y] = Max(mslit[x, y-1] + A[x, y], dp[x - 1, y] + A[x, y] + msr[x, y + 1])
と表すことができる（dp[x,y]は点(x,y)に来るルートの最大点）。
この合計値を求めて、最大のものを解答すればよい。パターン２も同様。

2017-11-22

Codechef November Challenge 2017 参加日記

143位/8136人で目標の2桁順位は達成できず。回答人数の多いCSUBQで部分点だったのが痛かった。以下、易問は省略する。

Periodic Palindrome Construction

長さNの文字列Sについて、Nが整数Pの倍数であり、かつSをPごとに分割したときすべてのP[i]が一致しているものを、周期がPである、と定義する。NとPが与えられたとき、文字aとbのみを使って、周期がPかつ全体で回文になる、長さNの文字列を作れ。ただし、文字列にはaとbの両方を使う必要がある。
1 <= P, N <= 10^5

UnionFindを使う。最終的な文字列をSとすると、全体で回文なので、
S[0] = S[len-1]
S[1] = S[len-2]...
とグループ化できる。
また、各分割文字列A,B...について
A[0] = B[0] ...
A[1] = B[1] ...
とグループ化できる。
全ての文字が同一グループになってしまったらImpossible、そうでないならグループごと適当にabを当てはめればよい。
https://www.codechef.com/viewsolution/16049370

Chef Hates Palindromes

アルファベットの最初のA文字のみを使い、長さNの文字列Sを作成せよ。このとき、最長の回文部分文字列をなるべく短くせよ。
1 <= N <= 10^5

まず明らかな観察として、A=1のときはaのみの文字列を返すしかなく、A>=3ならabcabcabc...を返せばよいことがわかる。よって、A=2の場合のみ考えればよい。
なるべく部分的な回文を短くしたいので、Nがある程度大きいなら
a|ab|b|ab|a|ab|...
のように構築すれば、最長の回文文字は長さ4になって最小となる。
("ab"で囲んでしまえば、その内部にある文字を中心とした回文は、それ以上大きくは作れないので)
Nが小さい(<=8)場合の回答はすべて列挙してしまうのが早い。
https://www.codechef.com/viewsolution/16058582

Chef and Intersection Line

チャレンジ問題。整数の配列A[M][N][N]が与えられる。このとき、二次平面上の点P[1],P[2],P[3],...P[M]を回答せよ。ただし
・P[i] - P[i - 1]の線は、それ以前のいずれの線とも交差してはならない（隣の線と一点でのみ一致する）
・k番目の点に(i, j)ついて、得点A[i][j][k]が加算される
・合計点をなるべく多くするのが目標
N = 50
1 <= A[k][i][j] <= 100
M = 50のテストセットと、M = 500のテストセットがある
制限時間は2.5秒
(テストケースの生成ロジックは省略）

以下の方針で90点程度の結果だった。
・有効解を貪欲的に作成する（点数はあまり気にしない）
・ランダムに点を選んで山登り
・次の点は、M=50のセットでは盤面のほぼすべてから、M=500は狭いので上下3ポイント以内くらいから選ぶ
盤面が100x100しかないので、M=500はかなり狭くあまり改善の余地がなかったように思う。
https://www.codechef.com/viewsolution/16235791

Chef and Subarray Queries

長さNの整数列Aと、整数L、Rが与えられる。Aの初期値はすべてゼロである。次のクエリに答えよ。
・タイプ１：A[x]をyに更新する
・タイプ２：Aの範囲[l, r]にあるサブ配列すべてにおいて、最大値がL以上R以下となるものの数を出力
1 <= N <= Q <= 5 * 10^5
1 <= L <= R <= 10^9
1 <= x <= N
1 <= y <= 10^9

本番では平方分割と二分探索を駆使して52ptの部分点だった。想定解はセグメント木を使う。以下の解説がわかりやすかった。
hamayanhamayan.hatenablog.jp
セグメント木のノードごとに
・Count：対応する要素数
・Answer：ノード単体での解答
・MinLeft/MinRight：ノード左(右)端に続く、連続するL未満の数の数
・MaxLeft/MaxRight：ノード左(右)端に続く、連続するR以下の数の数
の情報を持つ。すると、Answerは以下のように計算できる。

cur.Answer = left.Answer + right.Answer;
cur.Answer += left.Max_Right * right.Max_Left;
cur.Answer -= left.Min_Right * right.Min_Left;

MaxLeft/MaxRightを「連続するL以上R以下の数」にすると計算が面倒になってしまうようだ。
https://www.codechef.com/viewsolution/16282630

Product on the segment by modulo

長さNの整数列と整数Pが与えられる。以下のQ個のクエリに答えよ。
・区間[L, R]の要素すべての積 mod Pを出力
1 <= N <= 10^6
1 <= Q <= 2 * 10^7

本番では累積和（imos法？）的に解いたが、当然Pが素数でないと通らないので部分点だった。
想定解ではSparse tableのようにデータを持つ。
・A[k, i]: i以下で2^kの倍数となる最大のインデックスからiまでの積
・B[k, i]: iから、iより大きくて2^kの倍数となる最小のインデックスまでの積
こうすると、B[k, L]とA[k, R]で重複がないkを選ぶことができれば、各クエリに対してO(1)で回答できる。k=1から増やしていけば簡単に見つけることができる。（証明は公式Editorialにある：https://discuss.codechef.com/questions/116821/segprod-editorial)
Sparse tableはこちらが分かりやすかった。
http://tookunn.hatenablog.com/entry/2016/07/13/211148

Lovers Gift

N個の都市が、双方向に繋がった木の形のグラフで表される。都市はそれぞれ1からNでDistinctにスコア付けされる。次のクエリに答えよ。
クエリ１: 都市Cに銀行がオープンする
クエリ２: 都市Cから1つ以上の銀行を経由し、2番目にスコアの大きい都市を訪れる。ただし同じ道は通れない。このスコアを出力せよ
1 <= N, M(クエリ数) <= 100000

想定解は素集合を使って求める。この方法は本番でも思いついていたが、計算量が大きく不可能と判断してしまっていた。
・銀行がすべてオープンした状態にして、後ろからクエリを発行する
・銀行を経由しないグループを１つの集合とする
・集合ごと、「集合外で1番目と2番目に大きなスコア(m1とm2)」を管理する
・銀行がクローズするたび、集合をマージ
こうすれば、クエリ2ごとに
・Cに銀行があればN-2を解答
・それ以外ならm2を解答
すればよい。
マージ後のm1、m2は、単純にm1からデクリメントして探していく。これだと間に合わなそうだが、マージするたびにm1の初期値がどんどん小さくなるので問題ない。

2017-10-17

Codechef October Challenge 2017 参加日記

78位/10487人。これくらいの順位で安定するのが今年の抱負（改）。
以下、易問は省略する。

Chef and a great voluntary Program

リンゴa個、バナナb個をn人にいずれか一個ずつ配りたい。このとき、リンゴを配られた人は、直前x人が続けてリンゴだったら不満に思う。同じように、バナナを配られた人は、直前y人がバナナだったら不満に思う。不満を解消するには、リンゴまたはバナナを配る直前にキウイを渡せばよい。キウイの数を最小にせよ。
1 <= n <= 10^5
1 <= x, y <= n

a<=bとすると、配布の方法は2パターンしかない。
１、a, bひとつ以上, a, bひとつ以上...
２、bひとつ以上, a, bひとつ以上, a...
よって、aを一個ずつに分けて、その間にbを入れていけばよい。
https://www.codechef.com/viewsolution/15764132

Chef and Cycled Cycles

無向グラフを考える。このグラフにはN個のサイクルがあり、それぞれA[i]個のノードで構成されている。各サイクルにおいて、i番目のノードは(i + 1) % A[i]のノードとつながっている。さらに、グラフ全体をみると、N個のサイクルによって大きな１つのサイクルを構成している。つまり、i番目のサイクルは、i % N + 1番目のサイクルと、いずれかのノードで繋がっている。
すべてのエッジに重みが付いているとき、サイクルc1のノードv1と、サイクルc2のノードv2の最小コストを求めよ
なお、クエリ(c1, v1, c2, v2の組み合わせ）はQ個発行される。
1 <= N, Q <= 10^5
1 <= A[i] <= 10^5
1 <= A[1] + A[2] + ... + A[N] <= 10^5

単純なノードのみで構成されるサイクルn[0], n[1], ... n[k]を考えたとき、次のようにエッジコストの累積和を求めておけば、任意の2点間の最小コストはO(1)時間で求めることができる。
n[0], n[0]+n[1], ... Sum(n[0:k]), Sum(n[0:k])+n[0], ... 2xSum(n[0:k])
これを小さいサイクルと外側の大きなサイクルに適用すればO(1)で回答できる。
https://www.codechef.com/viewsolution/15784456

Chef and Magic Arrays

N個の数列があり、それぞれの数列は好きなようにシフトすることができる。このとき、i番目の数列の末尾の値をx、次の数列の最初の値をyとしたとき、|x - y|*iの合計値を最大化せよ。
数列の長さの合計は10^6を超えない
1 <= 値 <= 10^6

まず自明な観察として、実際に数列をシフトする必要はない。使うのは数列の先頭と末尾だけなので、ある位置jを末尾に使うとすると、先頭になるのはi+1である。
あとは次のDPを立てれば求めることができる。
dp[i, j]: 0..iまでで、数列iについて位置jを選んだときの最大値
https://www.codechef.com/viewsolution/15799713

(Challenge) Connecting computers

チャレンジ問題。ノード数1000の連結グラフを構築したときの最小コストを求めよ。
・各ノード間のコストはすべてランダムに与えられる
・各ノードについて、Degreeに応じたコストがかかる（Degreeの大小とコストの大小は連動しない）
制限時間はT=5で5秒。

Editorial想定解は連結を保持したままの山登り法。これが正解かなとは思ったが、連結を保持したまま高速に回すやり方が分からず保留（したままコンテスト終了）。次点解がクラスカル法＋αで、自分の実装もこれで平凡な得点に終わってしまった。

Shooting on the array

二次平面上にN本の部分直線がある。部分直線iは(i,0)から(i,A[i])へ引いてある。このとき、次のQ個のクエリに答えよ。
・+ i X => 直線iのA[i]をXだけ増やす
・? i L R => R-L+1本のX軸に平行なビームを発射する。j番目のビームは(i-0.5, L+j-1.5)から発射される。ビームは直線にぶつかると消える。このとき、ビームがあたる直線の本数をプリントせよ
1 <= N <= 10^6
1 <= Q <= 10^5
x <= X <= 10000
1 <= A[i] <= 10^9
1 <= L <= R <= 10^9

平方分割を使う。このとき、１つのセグメント内ではA[i]が増加している分のみ保持すればよい（それ以外のものはビームが当たりようがない）。するとセグメント内は単調増加になるので、現在のビーム範囲で当たる最も短い（左の）直線と、最も長い（右の）直線が二分探索で求められる。
計算量はO(QSqrt(N)LogN)でぎりぎり間に合う。
https://www.codechef.com/viewsolution/15803230