なつやすみ 42日目
昼夜逆転生活が続いている
- yukicoder埋め
No.303 割れません
かなり険しい問題 まずコーナーケースの処理から難しい
本題パートはフィボナッチ数のN番目の値を求めるというもの(N<=10^6)
一見簡単だが、modを取らないという異常問題
C++で多倍長を実装して、掛け算をNTTで処理しながら行列累乗すると通る - ABC218
A~Fを倒したところまでは良かったんですけどね……
D：Cを飛ばしたら幾何っぽいのが見えて焦る
y座標が等しい点同士で線分を全列挙してx座標で組み合わせた
E：やります
F：最短経路木が見えるからそれをうまく高速化するのかな？とか思った(可変全域木を解いたことがあったので) これってデータ構造とかで高速化できるんですかね？
C：悩んだけど結局黒い座標をsortして比較に落ち着いた
G：中央値は二分探索！つって木DPを書くけど合わない 結局解説ACになってしまった
binary_trie強いね もしかして最強のデータ構造ですか？
k番目が取得できるmultisetというだけで強いのにSetXORMinまで出来るのは偉い
なつやすみ 41日目
ほげ〜〜
- yukicoder埋め
0-1パズル 難しい 実装もむずい
サイコロで確率問題（2）
サイコロをN回振った時出た目の和が[L,R]に含まれる確率は？という問題(1<=N,L,R<=10^18)
AtCoderでは見ないタイプの知識を使った - yukicoder contest 313 う〜〜ん
D：面倒なので遅延セグ木で殴る
F：構文解析を一昨日初めて書いた人だったので気持ちよく解けた
ICPCとか予選で落ちるから出なくていいか〜つって構文解析の練習してないけどABCで出されても文句は言えないのだな……
G：負辺を含むMCFを一回も書いたことなかったから*1蟻本読んで実装しようとしたけどよく見たら計算量がO(E^2logV)になってて終わった……
結局ダイクストラを始める前にポテンシャルを計算しておけばいいのだなに
最大流も最小費用流も完全にブラックボックスとして使っているので何やってるかわからんになっていた
yukicoderのNo.1~No.300がある程度埋まった
残っているのは
- 強実装(重実装の幾何とか階乗埋め込みとかbit詰め込みとか)
- 強いアルゴリズム(最小シュタイナー木とかgarnerとかテトレーションとか)
- 普通に難しいやつ(解いたユーザー数15人以下)
とりあえず先に301~を埋めようと思います
*1:使う辺の本数が固定の場合は経験あるのでこれは嘘だが
なつやすみ 40日目
ついに40ですか 約2/3が終わってしまった……
- yukicoder埋めにハマった
貯金箱の焦り 遥か前に解説を見ていた(当時は解説の内容すら理解できなかった)
解法がとても鮮やか
ペガサス これも遥か前に(略)
これは想定解ではない方が鮮やか
そもそも長さNの順列のうち任意のiについて|p_i-p_(i+1)|!=1を満たすものの数え上げが難しい
カードゲーム(Hard)
これは解ける
傾向と対策：門松列（その3）
想定とは違うっぽい
包除によってminのmaxを全探索、内部でさらに包除
出席番号（2）
これは有名問題かな
next_permutation（1）
これ面白いね 勉強になりました
そのうちyukicoderのNo.1~No.300で解くべき問題10選みたいな記事書くかも(需要は……)
寝ます
なつやすみ 39日目
なんか10/3までなつやすみっぽい(まじ？)
薬学部さんは2年生の座学を対面、3年生の座学はオンラインとするらしい
正直大学行くの大変なのでオンラインなのは助かる
- なろうに生活を破壊されている 集中して読んでいると気づいたら午前6時みたいな感じ
- yukicoderを埋めている
サイコロで確率問題（1） 解説を見るはめに……
ループのある期待値DPなんだけどN<=10^18でdp[N]を計算しなきゃいけない
行列累乗+二分探索とか一次式にして行列累乗で係数を計算とか考えたけど誤差かTLが死ぬ
黒い文字列
根性でなんとかする
貯金箱の仕事
本質パートにたどり着くまでに時間がかかった 整数計画問題とか考えてたけど特に関係なかった 本質パートは何回か見ているので簡単
門松もどき
根性でなんとかする
最近Wi-Fiの調子悪くてう〜むという感じ
なつやすみ 38日目
う〜む
- ゲームセンターに久しぶりに行った チュウニズムを無限年ぶりにやったりしていた 全く上達の気配がなくて悲しい(というかプレイする頻度が全く足りていなさそう)
- あとは競プロしてた yukicoderの埋めをちまちまやっている
数学のテスト
微分を含む一変数の多項式を計算するだけ
初めて構文解析を書いた なんで動くのか不明だが通った
hel_world
犯罪の塊みたいな問題 考察はよくあるやつだけどオーバーフローと誤差処理と大量のコーナーケースを捌く必要がある
カードの数式
Ad-hocな解法があるけど制約が緩いせいで3冪のbitDPが通ってしまう bitDP方針の解説誰も書いてなかったし書いとこうかなと思ったけど全人類思いつきそうなのでやめた(面倒だし)
旅行してえ 計画立てようかな〜
なつやすみ 36日目
旅行行きて〜〜〜〜
- 親のポケモンGOの手伝いをする
- Educational Codeforces Round 112 (Div.2) バチャをした A~Eの5完
A：勢い余って謎DPを書く
B：長方形の敷き詰めが縦横独立になるの、ABCで見た記憶がある
C：全探索すると累積*2
D：2以上任意の長さの回文が存在しない⇔長さ2または3の回文が存在しない
Yukicoderで何回か見た記憶ある
E：Max-Minを最小化したいとき、にぶたんは微妙で、Minの全探索+差分更新が有効がち
区間を処理するデータ構造が必要になって、遅延セグ木を持ってくる
いきなり高度な知識が必要になったから非想定かと思ったら想定でびっくり
Codeforces、なんとなく全体的にTLが厳しいんだけどこれは何故なんだろう
F：とりあえずCactus-graphになることがわかる Tree-edgeかcycle-edgeかを見分けるためにUnionFindが必要なことがわかって書き始めるもサイクルに使われた辺を見分けるの無理じゃね？となって終了
解説を読む 確かに先読みして全域木を作ってその上で操作を考えてもいいことがわかる つまりHLDかEular tour+BITで検出できる
なるほど〜って感じ クエリ先読みして全域木を作るのは教育的かもしれない
もしかして通常のDiv.2とECRのDiv.2って難易度違う？
早く寝るか
