Codechef June Challenge 2018 参加日記
155位/438人(Div1)だった。もう1問くらい解けそうだったが、期間中にゲームを買ってしまったのが原因でフェードアウト敗退した。
三次元の座標上に、２つの点PとQ、および球が与えられる。Pは動かないが、Qは一定の速度で動いてゆく。時間tの点Qの位置は次の式で表される(dはベクトル、Q(0)はQの初期位置)。
Q(t) = Q(0) + d*t
はじめ、点QはPから見えないことが保証されている。このとき、点QからPが見えるようになる最小の時間を求めよ。なお、PやQが球に重なることはない。
初期状態は点Qが見えなくて、ある時間tから点Pが見えるようになるのだから、二分探索を使えば求められる。「点Qから点Pが見えるかどうか」は、Q->Pベクトルが球に交差する、と言い換えればよい。あとは初等幾何の問題。
https://www.codechef.com/viewsolution/18726175
n行m列のグリッドが与えれ、各セルにはタイプa[i,j]の花が咲いている。最大2種類の花を選び、その花のみ咲いている連続するセルを選択するとき、その最大面積を求めよ。上下左右のいずれかでセルが接するとき、その2セルは連続しているとする。
1 <= n, m <= 2000
1 <= a[i, j] <= 4x10^6
本番はむりやり通したが嘘解法。Editorialの貪欲解は、
１）あるセルと、そのセルの右または下のセルを選ぶ
２）その2つのセルにある色のみを選んでBFSしていく
を、すべてのセルに対して行っている。ただし、同じ集合が重複しないように、「現在のセルからある方向に遷移したことがあるか」をもって、もしあるならば無視するようにしている。これは自分の解とほぼ同じなのだが、重複を無視する部分が位置+色組み合わせでHashSetに入れて判断していたため、TLEになってしまっていた。方向だけなら配列で持てるので間に合う。
https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/editorialist/TWOFL.cpp
(Editorial解)
Codechef May Challenge 2018 参加日記
久しぶりのプロコンは今回からDiv1/2に分かれたCodechef。Div1で344位/633人の結果だった。ていうかDiv2でいいのに・・・。
サイズMの配列A、Bと整数Nが与えられる。次の最終resultを、10^9+7でModして答えよ。
result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]
1 <= M <= 10^5
1 <= N <= 10^5
いくつか列挙するとパターンが見える。たとえば
A = [ a, b, c ]
B = [ d, e, f ]
だとすると、iが1のときは
a, d, (a+d), (a+2d), (2a+3d), (3a+5d), (5a+8d), ...
a, e, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
a, f, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
のようになる。つまりAの各要素xについて
x * fib(n-3) * m
が最終回答になり、同様にBの各要素yについては
y * fib(n-2) * m
が回答になる。これを足し合わせればよい。（N<=2のときは別途計算）
https://www.codechef.com/viewsolution/18432901
要素がDistinctな整数列Aが与えられる。Aの要素Xがについて、次のサーチアルゴリズムで正しいXの位置が求められるようにするためには、最小で何回、要素を交換することが必要か。なお数列Aは１つのみだが、クエリはQ回問われる。
integer binary_search(array a, integer n, integer x):
integer low, high, mid
low := 1
high := n
while low ≤ high:
mid := (low + high) / 2
if a[mid] == x:
break
else if a[mid] is less than x:
low := mid+1
else:
high := mid-1
return mid
正しい二分探索経路上で、Xの左と右それぞれについて、
左：Xより大きいもの
右：Xより小さいもの
が交換しなけらばならない要素とわかる。まずこの左右から交換するべきなので、最終回答に左と右の差を加える。
その次に余ったもの（左もしくは右にあるもの）を、有効な要素と交換していけばよい。
有効な候補の有無は、あらかじめAをソートしておけばLowerBound/UpperBoundで効率よく探すことができる。
https://www.codechef.com/viewsolution/18435496
整数列Aの任意の要素に-1を掛けることができるとき、連続する長さ2以上の部分列が、必ず合計1以上になるようにしたい。最終的な数列の要素の合計を最小化せよ。
本番ではDFS+枝刈りで部分点だった。
よく考えると、ある要素iに注目しているとき、条件が成立するのは
・i-2が正、i-1が正
・i-2が負、i-1が正
・i-2が正、i-1が負
のパターンしかない。上からそれぞれdp_a, dp_b, dp_cとすると
dp_a[i] = min (dp_a[i-1], dp_b[i-1]) + A[i]
dp_b[i] = dp_c[i - 1] + A[i] (A[i] > A[i-1]のとき)
dp_c[i] = min (dp_a[i-1], dp_b[i-1]) - A[i] (A[i-1] > A[i] + A[i-2]のとき）
dp_c[i] = dp_a[i-1] - A[i] (a[i] + a[i-2] >= A[i-1] > A[i] のとき)
と式を立てることができる。
※参考実装
https://www.codechef.com/viewsolution/18500660
2018年の抱負（改２）
3月に妻が急病になり、ER搬送からの一週間入院という出来事があった（現在はもう問題なし）。それがきっかけで、自身の健康・キャリアついて色々考え直したので、今年の抱負も合わせて更新しておく。
2018年の抱負
一日7時間睡眠
必須科目。どんなに忙しくても6.5時間は寝る。健康は本当に大事
年収+15% → +10%
無理しない額に下方修正。睡眠を削ってまで達成しようとしないこと。
糸井重里さんの『ちゃんとメシ食って、風呂入って、寝てる人にはかなわない』を座右の銘とする。
dot.asahi.com
プロコン再開
もともと今年は控えるつもりだったが、熟考の末、日常的な趣味に戻すことにした。理由は
・プロコンをしないと、仕事のプログラミングを家でやってしまうことがわかった。。。
・アルゴリズムが自分の強みらしいとわかった。自分程度でも田舎の普通のプログラマの中だと突出する
・プロコンがないと、トップレベルのコーダーと絡む機会がゼロになることに気づいた
・ABC/ARCへの定期参加にメドがついた
などなど。
2018年の抱負（改）
2018年が2か月ほど過ぎたところで、今年の抱負を修正することにした。
まあ端的には、「ちゃんと寝る」と「年収増やす」が重すぎて、趣味にとても手が回らいことが判明しただけ。
2018年の抱負
一日7時間睡眠
強化科目。今のところ達成率が6割程度なので、せめて8割まで上げることにする。忙しい日も6時間は寝よう。
年収+15%
3月に昇給したので残り12%くらい。年末の定期昇給が去年と同じ8%と推定するなら、あと2回くらい特別昇給が必要な計算だ。
低レイヤ分野でレジュメにかけるレベルのアウトプットを何か
具体的には30日OS本と熱血アセンブラ本
これは上２つに比べると趣味的要素が強すぎるため、抱負からは外すことにした。
HackerEarth December Circuits '17 参加日記
2017年最後のプロコン。57位/5713人で風邪を引いていた割には悪くない。長期型プロコンだと、二桁順位がたまに取れるくらいの実力にはなったようだ。
同じ長さ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/
国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/
数列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/
N個の都市があり、それらをつなぐ道は全体でツリーを構成している。M種類のコンテストが各都市で開催される（１つのコンテストが複数の都市で開催されうる。ある都市では、あるコンテストが開催されないこともある）。ここで、
・連結したサブグラフを選び
・選んだサブセットで開催されるすべてのコンテストタイプに出場する
とする。この時、コンテストタイプの種類数kだけパスを購入しなければならない。
すべてのサブセットについてこのルールを適応したとき、パス数に対するサブセットの数を、すべてのkについて答えよ。
1 <= N <= 5000
1 <= M <= 10
解けそうで解けなかった問題。
dp[i, j] := 根をiとする木で、状態jになるサブグラフ数
と定義する。初期値を
dp[i, (開催されるコンテストマスク)] = 1
として、葉以外のノードについて、
のようにマージしていけば求められる。
計算は次のテクニックを使ってスピードアップできるらしい。
http://codeforces.com/blog/entry/45223（整数列のすべてのサブセットに対して、その合計を効率的に求める方法）
ノード数nの有向グラフ上を、Botがk個のインストラクションにそって移動する。インストラクションは、「現在地がノードxならノードyに移動せよ」というものであり、始めBotはノード1にある。ただし、移動中1回のみ、ランダムに隣のノードへBotが移動してしまうことがある。これは、インストラクションの前後いずれでも起こり得る（1度も起こらないこともある）。
このとき、最終到達地点としてありえるノードを答えよ。
1 <= n <= 100000
1 <= m, k <= 100000
本番ではDFS+メモ化で部分点だった。
ランダム変化がない場合の、ステップごとの位置を最初に算出する。そして、「現在のステップで最終的に到達する場所」をノードごとに保持しながら、うしろから処理していく。
（実装は省略）
2017年振り返りと2018年の抱負
2017の抱負と結果
SRMで黄になる→ LongContestで二桁安定 (30%)
Topcoderがアレなので途中で変更した抱負。二桁順位は30%くらいの確率なので達成率も30%。
- 熱で寝込まない (100%)
風邪は引いても寝込んではいない。すばらしい成果。
- ちゃんと寝る (20%)
連続で5時間睡眠を何度かやってしまった。
2018年の抱負
- 一日7時間睡眠
いいかげん睡眠不足になっていい歳じゃない
- 年収+15%
去年は+8％だったのでかなりアグレッシブ
- 低レイヤ分野でレジュメにかけるレベルのアウトプットを何か
具体的には30日OS本と熱血アセンブラ本
プロコンはちょっと控えめにする予定。
HackerRank Week of Code 35 参加日記
1044位/9458人の酷い結果。以下、易問は省略。
HxWの平面上の各セル上に、立方体がいくつか積み重なっている。外部に面している面積を求めよ。
X面からみた面積、Y面からみた面積、Z面からみた面積をそれぞれ求めて足せば良い。
https://www.hackerrank.com/contests/w35/challenges/3d-surface-area/submissions/code/1304126485
n行m列のマトリックスがあり、各セルには点数が設定されている。1行目の任意のセルから、n行目の任意のセルまで移動したとき、得られる合計得点の最大値を求めよ。ただし、セルの点数は通過後にゼロになる。また、セルからの移動は左右と下のみ可能である。
1 <= n x m <= 4 * 10^6
3日考えて解けなかったDPの問題。これは悔しい。
移動制約により、ある点に到着するルートは2通りしかない。
パターン１：ある点より左いずれかに降りてきて、点を通過して右から戻ってくる（通過しない場合も含む）
パターン２：ある点より右いずれかに降りてきて、点を通過して左から戻ってくる（通過しない場合も含む）
パターン１だけ考えてみる。
上の矢印で表されるのは、「その行だけを考えたときの、(x, y)より右の合計最大値」であり、
msr[x, y] = Max(msr[x, y + 1] + A[x, y], 0)
と表すことができる。
上の矢印で表される部分を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)に来るルートの最大点）。
この合計値を求めて、最大のものを解答すればよい。パターン２も同様。
