Blueberry1001

競プロer

Blueberry1001

競プロer

6/4

雨上がりって良いよね 解いた問題1 少し前のARCのC。コンテスト後に解説を見た覚えはあったが解法は覚えていなかった。普通にDPをするだけ、天才…次に活かせるようにし…

Blueberry1001
Blueberry1001
1か月前
1

5/31

余裕のある人間になりたい 解いた問題 AGC-黄。bit全探索が見えるが判定にO(N^2)ぐらいかかるので間に合わない。他のこともしつつ4時間ほど考察をしたが解法は浮かばず……

Blueberry1001
Blueberry1001
1か月前
1

5/30

5月があと1日で終わってしまう～ 解いた問題1 AGCの黄Diff。思ったより簡単だった、というかこういう数え上げは得意なのかも？寄与を考えるみたいなことをすればよい 解…

Blueberry1001
Blueberry1001
1か月前

5/29

忙しい充実した一日だった。 今日のアルゴリズム：なし 簡易LARSCHをちょっと眺めて、「こんなんで本当にできるのか…？」をしただけ。明日は簡易LARSCHを使ってABC355G…

Blueberry1001
Blueberry1001
2か月前
1

5/28

寝坊した。 今日のアルゴリズム：Monotone Minima （直接貼ると重いのでリンク）https://speakerdeck.com/tatyam_prime/monge-noshou-yin-shu tatyamさんの「Mongeの手…

Blueberry1001
Blueberry1001
2か月前

5/27

お久しぶりです。ぴったり1か月空いたらしい。 日々の精進の記録あるとやっぱり良いなと思ったので再開してみます。またすぐ更新途絶えるかもしれないけどできるだけ続けら…

Blueberry1001
Blueberry1001
2か月前
2

4/27

この記事はABC351の直後に書いています。あんまり読んでいてたのしい記事ではないと思うので読まなくて良いです。それでも読みたいという物好きの方、ありがとうございます…

Blueberry1001
Blueberry1001
3か月前
6

4/23

雨でした。 今日のアルゴリズム クエリ平方分割です。前回のABC-Gで出た。平方分割の考え方をクエリに適用する方法を考える感じかな 解いた問題 クエリ平方分割の練習…

Blueberry1001
Blueberry1001
3か月前
1

4/22

けっこう期間が空いちゃった。書きたくなったので再開 今日のアルゴリズム 新しい知識に触れるのは良いこと。というわけで今日はLowlinkです（今更） いや～酷い。これ…

Blueberry1001
Blueberry1001
3か月前
1

4/16

頭が痛いです。 解いた問題 O(ND^3)がすぐに見えますが流石に捨てます。遷移先が斜めに連続しているので斜めに累積和をとっておけばO(ND^2)におさまりそうです。TLを見る…

Blueberry1001
Blueberry1001
3か月前
1

4/15

仮入部二回目でした。あんまり新しい人は来ませんでしたが、前回来た人たちが今回も来てくれて嬉しい 解いた問題 DP。こういうパターンのDPを部分列DPと言うらしい…？あ…

Blueberry1001
Blueberry1001
3か月前
3

4/14

日曜日でした。 解いた問題 どこからどう見ても最小カットですね。ところで復元はどうするんでしたっけ…？となっていました。ACLは復元も含めてできるらしいです。すご…

Blueberry1001
Blueberry1001
3か月前
2

4/13

ABCでした。Eでしょうもないミスでひたすら時間を溶かしてしまった、大反省… しょうもないミスをしないようにするために朝練などで場数を踏んでいるのになぜ改善できない…

Blueberry1001
Blueberry1001
3か月前
1

4/12

1日サボったのはわざとです。たぶん。 今日は1年生の仮入部初日でした。かなりうまく行って良かった。 解いた問題1 EDPC最終問題。 ちゃんとした（単調性がない）CHTもラ…

Blueberry1001
Blueberry1001
3か月前
1

4/10

新学期です！！後輩がたくさん入学してきた。TCAにも既に6人が入部を確定させていて嬉しい限りです。 解いた問題1 ABC-橙 フローにしか見えない…絶対フローだこれ…から…

Blueberry1001
Blueberry1001
3か月前
2

4/9

今日は入学式。明日から新学期です。高2になります。 解いた問題1 それぞれの点の寄与を考えて、包除原理かなあ…でも同じ座標にある点の処理がめんどいしなあ…と思って…

Blueberry1001
Blueberry1001
3か月前
2
Blueberry1001

Blueberry1001

6/4

雨上がりって良いよね

解いた問題1

少し前のARCのC。コンテスト後に解説を見た覚えはあったが解法は覚えていなかった。普通にDPをするだけ、天才…次に活かせるようにしたい

解いた問題2

典型90から。xor基底を出してどうする？と思ったら、基底じゃない奴は使う/使わないを選べるから最終的な答えが2倍されるみたいな話だった。xorとはいえ数値ではなくvectorなのでsetにしていろいろ頑張

もっとみる
Blueberry1001

Blueberry1001

5/31

余裕のある人間になりたい

解いた問題

AGC-黄。bit全探索が見えるが判定にO(N^2)ぐらいかかるので間に合わない。他のこともしつつ4時間ほど考察をしたが解法は浮かばず…
解説を見ると天才が書いてあった。ABC355Fの話と少しだけ似ていると思った。ある数字を消して、答えが構築できなくなったらその数字は必須、みたいな条件を使うとうまくできる。

まとめ

明日はABC。ABC前に行事があっ

もっとみる
Blueberry1001

Blueberry1001

5/30

5月があと1日で終わってしまう～

解いた問題1

AGCの黄Diff。思ったより簡単だった、というかこういう数え上げは得意なのかも？寄与を考えるみたいなことをすればよい

解いた問題2

2-SATを使うんですね！…どう使うんですか？となって解説を見た。2-SATはあまり見かけない気がするがいつか役に立つときが来るだろう

解いた問題3

最大流ですね！…どう使うんですか？となって解説を見た。二

もっとみる
Blueberry1001

Blueberry1001

5/29

忙しい充実した一日だった。

今日のアルゴリズム：なし

簡易LARSCHをちょっと眺めて、「こんなんで本当にできるのか…？」をしただけ。明日は簡易LARSCHを使ってABC355Gを解説ACしようかな

解いた問題1

ARC青。どちらの花束でも、2種類を一本ずつは使うのでまずはそれを引いてみると見えやすい。二分探索。

解いた問題2

全然わからんので解説を見た。区間DP、天才か…となった。

もっとみる
Blueberry1001

Blueberry1001

5/28

寝坊した。

今日のアルゴリズム：Monotone Minima

（直接貼ると重いのでリンク）https://speakerdeck.com/tatyam_prime/monge-noshou-yin-shu

tatyamさんの「Mongeの手引き書」を読み進めた。Monotone Minimaは、一度だけ使ったことがありましたがほとんど仕組みを理解していなかった。今日このスライドを読んで完全

もっとみる
Blueberry1001

Blueberry1001

5/27

お久しぶりです。ぴったり1か月空いたらしい。
日々の精進の記録あるとやっぱり良いなと思ったので再開してみます。またすぐ更新途絶えるかもしれないけどできるだけ続けられたらいいなと思っています。日記を書いていると、「日記に書ける程度の精進はしたい」って意識も生まれますし！

今日のアルゴリズム：黄金分割探索

前回のABC-Gを理解するうえでさまざまな知識が必要になることがわかったので、一つ一つ理解し

もっとみる
Blueberry1001

Blueberry1001

4/27

この記事はABC351の直後に書いています。あんまり読んでいてたのしい記事ではないと思うので読まなくて良いです。それでも読みたいという物好きの方、ありがとうございます

言い訳から入ろうか　いや、まずは結果を

ひどい語彙力をしているが、本当にこれしか感想が無い。
いや、CとDで地味に沼ったなあというのはあったけど解法が見えなかったわけではないので。

問題はE。「マンハッタン距離は45度回転」と

もっとみる
Blueberry1001

Blueberry1001

4/23

雨でした。

今日のアルゴリズム

クエリ平方分割です。前回のABC-Gで出た。平方分割の考え方をクエリに適用する方法を考える感じかな

解いた問題

クエリ平方分割の練習用に前回のGを解いた、というかクエリ平方分割を使う問題があまり出てこなかった。別解として出ることが多いのかな…？

解いた問題2

畳み込みです！知らね～～
ちゃんと理解しないとな…

まとめ

明日はLinkCutTreeのつ

もっとみる
Blueberry1001

Blueberry1001

4/22

けっこう期間が空いちゃった。書きたくなったので再開

今日のアルゴリズム

新しい知識に触れるのは良いこと。というわけで今日はLowlinkです（今更）

いや～酷い。これ学んだって言えるのだろうか…
とりあえず使えなくはない…？よくわからない…

典型90

bitDPやるだけ。
O(DN2^N)で書いて、あ～これO(D(2^N+N))になるなあと思って高速化したら大して変わらず。9倍ぐらい速く

もっとみる
Blueberry1001

Blueberry1001

4/16

頭が痛いです。

解いた問題

O(ND^3)がすぐに見えますが流石に捨てます。遷移先が斜めに連続しているので斜めに累積和をとっておけばO(ND^2)におさまりそうです。TLを見ると6secなので間に合います。実装…できません！！！！！
斜めに遷移するDPに慣れていないので実装ができない、というか頭が壊れる。落ち着いて紙に書いて整理するのが重要そうだが…

まとめ

タイピングが最近早くなってきて

もっとみる
Blueberry1001

Blueberry1001

4/15

仮入部二回目でした。あんまり新しい人は来ませんでしたが、前回来た人たちが今回も来てくれて嬉しい

解いた問題

DP。こういうパターンのDPを部分列DPと言うらしい…？あまり得意では無さそうなので対策しておきたい。

まとめ

あとEDPCを3問解きました。朝練もいつも通り。
ゼータ変換を履修したい

Blueberry1001

Blueberry1001

4/14

日曜日でした。

解いた問題

どこからどう見ても最小カットですね。ところで復元はどうするんでしたっけ…？となっていました。ACLは復元も含めてできるらしいです。すごい。

まとめ

あと、素因数分解を3倍高速化（2と3を先に処理する）しました。日曜日は一応休むのを重視しているつもりです。スニペットの整理をしたいなあって最近思っているのですが手を付けられていない。あ、EDPCもう一周やらないと！

Blueberry1001

Blueberry1001

4/13

ABCでした。Eでしょうもないミスでひたすら時間を溶かしてしまった、大反省…

しょうもないミスをしないようにするために朝練などで場数を踏んでいるのになぜ改善できないのか…
普段から、しそうなミスを意識しながら実装するようにしてみようかなと思う。

Blueberry1001

Blueberry1001

4/12

1日サボったのはわざとです。たぶん。
今日は1年生の仮入部初日でした。かなりうまく行って良かった。

解いた問題1

EDPC最終問題。
ちゃんとした（単調性がない）CHTもライブラリ化しておきたいなという気持ちになった。

解いた問題2

ABC-橙
Aを全探索すると条件にハマるBはN-1-Aの約数なので全探索…できない！困った！！
解説を見るとA-Bを全探索し、ずらすのをうまくO(1)でやって

もっとみる
Blueberry1001

Blueberry1001

4/10

新学期です！！後輩がたくさん入学してきた。TCAにも既に6人が入部を確定させていて嬉しい限りです。

解いた問題1

ABC-橙
フローにしか見えない…絶対フローだこれ…から全く考察が進まず…
辺の貼り方はやっぱりいろんな問題を解いて身に着けていくしかなさそう。というか、ちゃんと解けなかった時に辺をどうしてそういう貼り方をしているかをしっかり理解した方が良さそうだなあ。

解いた問題2

EDPC

もっとみる
Blueberry1001

Blueberry1001

4/9

今日は入学式。明日から新学期です。高2になります。

解いた問題1

それぞれの点の寄与を考えて、包除原理かなあ…でも同じ座標にある点の処理がめんどいしなあ…と思っていたら同じ座標にある点が制約で省かれていた（制約はちゃんと読もう）
2次元動的BITで点を管理するとTLEしたのでx昇順/x降順で二回、セグ木を使いながら走査して、各点の左上/右上/左下/右下にある点の個数を数えた。平面走査っぽいかも

もっとみる