2018-12-09

JOI2018/2019予選 E - イルミネーション (Illumination)

問題

https://joi2019-yo.contest.atcoder.jp/tasks/joi2019_yo_e

解法

まず{(L,R)}の前処理をします。サイズNのリストを用意して自分が入っている区間[L,R]のうちRが最大のもので初期化をします。どの区間にも入っていなければ0です。

f:id:kgtkr:20181209181842p:plain

ただ普通に実装するとO(MN)で間に合わないので工夫が必要です。まず{(L,R)}(以後LRと呼ぶ)をR→Lの優先順位で降順ソートします。次に用意したリストを右から埋めていく(既に埋めた所は埋めない)をしていくとO(N)となり間に合います。疑似コードは以下のような感じです。

let m_list = make_vec(init=0,len=N);
my_sort(LR) // my_sortはLRをR→Lの優先順位で降順ソートする関数

let cur = N;
for (l, r) in LR {
    for i in range(l,min(cur-1, r)) {
        m_list[i] = r;
    }
    cur = min(cur, l);
}

これで前処理は終わりです。この前処理したリストをm_listと呼ぶことにします。次はメインの処理です。これはi番目以降のツリーの美しさの最大値という一次元DPで実装出来ます。 i番目に置く場合と置かない場合のmaxを取ればいいです。よくあるやつですね。置く場合はさっき前処理したやつを使います。 iに飾ってしまうと入っている区間の最大のRまでは飾る事が出来ません。よってmax(i,m_list[i])+1以降しか飾れない事がわかります。(iとのmaxを取っているのはどの区間にも入っていない場合0となるため) よって以下のような疑似コードとなります。

f(i){
    if(i>=len(A)){
        0
    }else{
        max(f(i + 1),A[i] + f(max(i, m_list[i]) + 1))
    }
}

あとはこれをメモ化すればおしまいです。

ソース

解説するよりソース見たほうが早そうなので置いておきます。 https://github.com/kgtkr/procon/blob/master/atcoder/rust/joi2019_yo_e/src/main.rs

2018-10-13

n^0+n^1+n^2が6a+5の倍数でない事の証明

何かツイート流れてきたので

特に高い物の証明が出来る腕は無いが、
n^0+n^1+n^2(n:自然数)は5,11,17,23,29の倍数にはならぬらしい。
— 柏木 (@kasiha_ki) 2018年10月13日

以降41,47,53,59,71,83,89,101,107……。畑違いの身には全く解らぬ。
— 柏木 (@kasiha_ki) 2018年10月13日

ゆるぼ
n^0+n^1+n^2(n:自然数)が5,11,17,23,29の倍数にならないという証明
— 和差積商🍀🌈🎵 (@mofmof_hana) 2018年10月13日

証明

$n,\ a$ が整数の時、 $n^0+n^1+n^2$ 、すなわち $n+n^2$ が $6a+5$ の倍数にならないことを証明する
$6a+5$ の倍数は $k$ を整数とすると $(6a+5)k$ と表す事が出来る
$1+n+n^2$ が $6a+5$ の倍数だと仮定すると、
$1+n+n^2=(6a+5)k$
$n,\ a$ が $5$ の倍数の時、 $p,\ q$ を整数とし $n=5p$ 、 $a=5q$ とすると、
$$
\begin{eqnarray}
\mbox{(左辺)} &=& 1+5p+(5p)^2 \\
&=& 1+5p+25p^2 \\
&=& 1+5(p+5p^2)
\end{eqnarray}
$$

$$
\begin{eqnarray}
\mbox{(右辺)} &=& (6 \cdot 5q + 5)k \\
&=& 5k(6q+1)
\end{eqnarray}
$$
よって左辺は $5$ の倍数でない、右辺は $5$ の倍数となり矛盾する
よって $n^0+n^1+n^2$ は $6a+5$ の倍数ではない

2018-09-20

差分リスト式変形

メモ

-- リスト(右結合)
[1,2,3,4,5] ++ ([6,7] ++ [8])
[1,2,3,4,5] ++ [6,7,8] -- コスト2(合計2)
[1,2,3,4,5,6,7,8] -- コスト5(合計7)

-- リスト(左結合)

([1,2,3,4,5] ++ [6,7]) ++ [8]
[1,2,3,4,5,6,7] ++ [8] -- コスト5(合計5)
[1,2,3,4,5,6,7,8] -- コスト7(合計12)


-- 差分リスト(右結合)
fromDiffList(toDiffList [1,2,3,4,5] <> (toDiffList [6,7] <> toDiffList [8]))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> ((\b->[6,7] ++ b) <> (\c->[8] ++ c)))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> (\x->(\b->[6,7] ++ b) ((\c->[8] ++ c) x)))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> (\x->(\b->[6,7] ++ b) ([8] ++ x)))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> (\x->[6,7] ++ ([8] ++ x)))
fromDiffList((\y->(\a->[1,2,3,4,5] ++ a)) ((\x->[6,7] ++ ([8] ++ x)) y))
fromDiffList((\y->(\a->[1,2,3,4,5] ++ a)) ([6,7] ++ ([8] ++ y)))
fromDiffList(\y->[1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y)))
(\y->[1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y))) []
[1,2,3,4,5] ++ ([6,7] ++ ([8] ++ []))
[1,2,3,4,5] ++ ([6,7] ++ [8]) -- コスト1(合計1)
[1,2,3,4,5] ++ [6,7,8] -- コスト2(合計3)
[1,2,3,4,5,6,7,8] -- コスト5(合計8)

-- 差分リスト(左結合)

fromDiffList((toDiffList [1,2,3,4,5] <> toDiffList [6,7]) <> toDiffList [8])
fromDiffList(((\a->[1,2,3,4,5] ++ a) <> (\b->[6,7] ++ b)) <> (\c->[8] ++ c))
fromDiffList((\x->(\a->[1,2,3,4,5] ++ a) ((\b->[6,7] ++ b) x)) <> (\c->[8] ++ c))
fromDiffList((\x->(\a->[1,2,3,4,5] ++ a) ([6,7] ++ x)) <> (\c->[8] ++ c))
fromDiffList((\x->([1,2,3,4,5] ++ ([6,7] ++ x))) <> (\c->[8] ++ c))
fromDiffList((\y->(\x->([1,2,3,4,5] ++ ([6,7] ++ x))) ((\c->[8] ++ c) y)))
fromDiffList((\y->(\x->([1,2,3,4,5] ++ ([6,7] ++ x))) ([8] ++ y)))
fromDiffList((\y->([1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y)))))
(\y->([1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y))))
([1,2,3,4,5] ++ ([6,7] ++ ([8] ++ [])))
([1,2,3,4,5] ++ ([6,7] ++ [8])) -- コスト1(合計1)
([1,2,3,4,5] ++ [6,7,8]) -- コスト2(合計3)
[1,2,3,4,5,6,7,8] -- コスト5(合計8)

2018-08-22

順序が変化するデータのページング処理について考えてた(個人的メモ)

今回のデータ

(id,update)

ページング処理は大変

要素が追加されていくだけのデータであればページング処理は簡単です。追加されたdateなどをキーにしてlimitするだけで出来ます。
しかしupdateをキーにしたい時などは上手いことしないと抜けが発生します。
まあやったことある人なら分かると思います。 elasticsearchのscrollAPIとか使えば出来ますが…あれスナップショットの有効期限とか設定する必要があるので好きじゃない。永続的に使いたい

今回やること

add(id=1,update=1)
add(id=2,update=2)
add(id=3,update=3)
get(key=INF,limit=2)
update(id=1,update=4)
get(key=2,limit=2)

単純にやると

1,2,3

id	update
3	3
2	2
1	1

4(result)

id	update
3	3
2	2

5

id	update
1	4
3	3
2	2

6(result)

(なし)

本当は以下のデータが欲しい

id	update
1	1

どうする

書き換えるのではなく追記方式(不変的な)にすればデータ的には残ってるので正常に取得出来るはず効率の良いクエリがあるかは知らない(考えます)

5

id	update
1	4
3	3
2	2
1	1

2018-06-18

AGC024-A Fairnessの考察

AGC024-A Fairnessの考察を頑張って書いたので残したいなと。
解説の解き方とは全く違う解き方をしたけど答えは同じになったので数学って凄いなと思いました(こなみ)

あとwolframalphaってのが凄い。
複雑な式変形とか漸化式も自動で解いてくれる。競プロでDPしたい時とか使えそう。

って事で考察です。

k回操作後のa,b,cの値をそれぞれ
fa(k),fb(k),fc(k)
とする
a,b,cはfa(0),fb(0),fc(0)
を表す事とする

操作を行っていくとa,b,cはそれぞれ
fa(0),fb(0),fc(0)=a,b,c
fa(1),fb(1),fc(1)=b+c,a+c,b+c
fa(2),fb(2),fc(2)=2a+b+c,a+2b+c,a+b+2c
fa(3),fb(3),fc(3)=2a+3b+3c,3a+2b+3c,3a+3b+2c
fa(4),fb(4),fc(4)=6a+5b+5c,5a+6b+5c,5a+5b+6c
となっていく

fa(k),fb(k),fc(k)のa,b,cの係数を
(fa(k)のaの係数,fa(k)のbの係数,fa(k)のcの係数)(fb(k)のaの係数,fb(k)のbの係数,fb(k)のcの係数)(fc(k)のaの係数,fc(k)のbの係数,fc(k)のcの係数)
とすると

k=0: (1,0,0)(0,1,0)(0,0,1)
k=1: (0,1,1)(1,0,1)(1,1,0)
k=2: (2,1,1)(1,2,1)(1,1,2)
k=3: (2,3,3)(3,2,3)(3,3,2)
k=4: (6,5,5)(5,6,5)(5,5,6)
となる

k回操作後の係数を
(f(k),g(k),g(k))(g(k),f(k),g(k))(g(k),g(k),f(k))
とすると

f(0)=1
g(0)=0
f(k+1)=g(k)*2
g(k+1)=f(k)+g(k)
という連立漸化式を得られる

これを解くと
f(k)=1/3(2(-1)^k+2^k)
g(k)=1/3((-1)^(1+k)+2^k)

また、fa(k),fb(k),fc(k)の値は
fa(k)=f(k)a+g(k)b+g(k)c
fb(k)=g(k)a+f(k)b+g(k)c
fc(k)=g(k)a+g(k)b+f(k)c
である

求める値は
fa(k)-fb(k)
=(f(k)a+g(k)b+g(k)c)-(g(k)a+f(k)b+g(k)c)
=f(k)a+g(k)b-g(k)a-f(k)b
=f(k)(a-b)+g(k)(b-a)
=1/3(2(-1)^k+2^k)(a-b)+1/3((-1)^(1+k)+2^k)(b-a))
=(-1)^k(a-b)

よって
kが偶数の時:a-b
kが奇数の時:b-a

2018-06-17

AtCoderで水色になりました

ABC100で水色になりました。せっかくなので色々振り返ってみようと思います

競プロを始めるまで

主にWebプログラミングをやってました。というか今もやってますし、ずっとこっちがメインです。 Webと競プロはかなり文化が違うので競プロはかなり戸惑いました。かなり昔にpaizaとか少しやった記憶ありますが全く解けませんでした。

初めてのコンテスト

初めてのコンテストは9/23の「CODE FESTIVAL 2017 qual A」、たまたまTLに流れて来たちょくだいさんのツイートに反応したらリプとフォロー貰えて嬉しかったので試しに参加してみました。言語はJS、結果は1完で初期レート14。流石に無理だと思いしばらく競プロは放置していました。

初めてのABC

12月頃になると、何故か競プロerとかなり関わるようになりました。そして12/23に始めてのABC、「ABC083」に参加しました。結果は3完。思っていたより解けたので楽しくなってきてABCは毎回出るようになりました(今の所ABCは皆勤です)。途中でAPCも出ました。

Rust

C++が怖いのでCF2017以外のコンテスト本番は全部Rustで出ています。速くて書きやすいので最高。そもそも競プロを初めた理由の半分くらいはRustの勉強だったり。入力値パーサーのマクロやサンプルケースから自動でRustのテストコードを吐くユーザースクリプトを作ったりしました。あとはライブラリ整備。ただ競プロの情報が少ないのと、競プロerで出来る人がほとんどいないのが辛い

精進

2回くらいバチャに参加して、精進botで1位取るためにA問題埋めまくって()、C・Dを少し埋めました。とりあえずC、DとAGCのAは埋めたい。

書籍

2/10に蟻本を買って軽く読み流して少しだけRustに移植しました。めちゃくちゃ分かりやすかったです。螺旋本とチーター本も欲しい。

覚えたアルゴリズムとか

幅優先探索
ダイクストラ
累積和
gcdとか素数列挙、約数、素因数分解とか
クラスカル法
Union Find
ワーシャルフロイド

覚えたって書きましたが嘘です。全く覚えていませんし書けと言われてもgcdくらいしか書けません。全部ライブラリ化してしっかりテストしてコピペで使えるようにしました。本番で実装したくない…

これから

ABCはratedじゃなくなりました。はい。 AGCもARCも参加回数0(nosubmit撤退はあるが)なのでかなり怖い。スプラのウデマエ上がった時みたいにボコボコにされるんだろうなと思ってます。とりあえず蟻本を読み直して、500点問題は安定させたいです。水色中盤(1400)目標で頑張ります。受験なんて知らねぇ

tkrの日記

プログラミングの事など