zero’s notepad

メモ帳

2022年まとめ

概要

競技プログラミングの自分自身における振り返りをします。

レート差分

  • Atcoder: 955 -> 906 (-49)
  • Codeforces: 1222 -> 1326 (+104)
  • Codechef: 1624 -> 1614 (-10)
  • Topcoder: ???(出た記憶なし...)

問題数

Solved By zezero
AtCoder: 1734 (+383)
Codeforces: 194 (+65)
AOJ: 17 (+1)
yukicoder: 79 (+30)
CodeChef: 33 (+33 new)
TopCoder: 3 (+0)
Total: 2060 (+512)

特筆事項

競技Longest Streak終了。これは逆によかったかもしれません。
この一年緑で停滞
ABCのEFが解けない
ABCのCDが解けずにコンテスト終了して負けるときがある
ABCDの序盤の速度差による微減少

反省

  1. 適切な難易度の問題を解いていますか？
  2. コンテスト後の問題は復習していますか？
  3. コンテスト中の限られた時間で解けるように意識していますか？
  4. コンテストだけ出ても成長しないらしいです

Atcoder Problemsよりのzezeroの記録（2022/12/31時点）

Difficulty Pies
Unique AC Heatmap
MAX difficulty Heatmap

Spring Challenge 2022 参加記

拝啓

肌寒いけど、いかがお過ごしでしょうか。

結果

Global rank: 3408 th / 7695
League rank: 888 th / 2113

戦績

感想

Spring Challenge 2021以来の参加。自分ベースをしっかり守ればいいゲームかと思ったけれども実際は攻撃しなければ取り返しのつかなくなるゲームであった。 （Siｌverボスにより判明）実装しながら考えたほうが進捗は生まれるかもしれん? BOT PROGRAMMING 最高！Fall Challenge 2022もBOT PROGRAMMINGで頼む！！！

PS

以下は競技中のメモである。

SpringChallenge2022

2022/4/25

wood div1 昇格
後手のときバグってます笑
Readmeに書くべきか？
みんなで一緒に倒すのが最大火力で最適かも

2022/4/26

何もしてません
bronze 昇格
スペルでサッカーしていてバトルドームを感じた

2022/4/27

SPELLにSHIELDとCONTROLがあるが使い道がわからん
守りに入るだけではwild manaで負ける（自分領域外にいた時間）
攻めができない（実装）

2022/4/28 ~ 2022/4/30

なにもしてませんｗ

2022/5/1

終わりの時間が近いことに気づく
CONTROLでちまちま敵ベースに送りつける
オフサイドしまくりの敵が強すぎる

2022/5/2

silverに昇格
Bossは前半マナため、後半にヒーロー妨害という戦略
やはり速攻サッカーゲーか？

敬具

競技プログラミング２年目

拝啓

8/23をもって競技プログラミング２年生を終えるらしいので振り返ってみる。
ポエムです。

スクリーンショット集

f:id:zezero:20210821181015p:plain
Atcoder Problemsより
f:id:zezero:20210821181012p:plain
Atcoderプロフィールより

感想

緑になっている。えらい
約1年前と比較すると順位は下がっている。涙
Rating分布というボタンが追加されている。
TEEというrating 4000の人だったら何秒かかるという推定値が追加されている
約1年前 zezero.hatenablog.com

主な出来事（自分が印象に残ったこと）

2020/9/7 Atcoder Library 公開
2020/10/3 ARC再開(ARC104)
2020/12/26 AGC050(Good Bye rng_58 Day 1)
2020/12/27 AGC051(Good Bye rng_58 Day 2) 以後 admin rng_58 -> maroonrkとなる
2021/3/6 AHC始動 (AHC001) 初のratedマラソン。ヒューリスティックと呼称
2021/3/30 競プロ典型90 開始 期間中毎日典型問題が公開される
2021/7/11 競プロ典型90 終了
2021/7/31 ABC 問題数6問から8問になる(ABC212)
2021/8/4 競プロ典型90 常設コンテストに追加
3020/2/29 AGC042 (based on World Tour Finals)
新型コロナウイルスのため開催中止に。この問題セットはGood Bye rng_58に使用されたようである。 「おじいちゃん。なんでAGC042がないの？」と聞かれたときにどうかこの記事を思い出してほしい。

P.S.

競技プログラミング年表おもしろそう。ただAtcoderしか書けていないのはどうだろうか。ちなみにopen-then-rated(問題見たらrated)の議論はこの期間に行われておりました。わりと１年で色々変わりましたね。すごい

敬具

パスカルの三角形メモ

F - Many Many Pathsを解いててパスカルの三角形おもしろと思ったのでメモる。

メモです。内容が乏しい。

以下のDPテーブルを考える。

f:id:zezero:20210303011720p:plain
DPテーブル
このDPテーブルは各グリットの最短経路の個数を示す。（0-indexed)

すなわちdp[i][j] = comb(i+j,j)である。

(comb(x,y) = \binom{x}{y} を表す。)

このテーブルで(0,0)を一番上に来るように回転させて見るとパスカルの三角形の一部が現れる。

自明な性質

dp[i][j] = dp[i-1][j] + dp[i][j-1]

dpの配り方から明らか。あるマスは左のマスと下のマスの和である。（範囲外は0と考えてよい。ただしdp[0][0]=1である。）

ふーんなるほどね

\displaystyle{ \sum_{k=0}^{n} dp[k][n-k] = 2^n }

これは二項定理を考えるとわかりやすい。

(1+x)^ nを展開したときの多項式の係数がそれぞれdp[i][n-i]に一致する。 ここでx=1とすると上式が導ける。

あるいはbit全探索を思い出してほしい。生成可能な長さnのビット列において１が立っている個数がi個であるビット列はいくつか？ という問に対して、dp[i][n-i]である。0 <= i <= nであるからして全部数えたら 2^ nである。

これはD - Knightで学んだ記憶がある。

どうして

\displaystyle{ \sum_{i=0}^{x}\sum_{j=0}^{y} dp[i][j] = dp[i+1][j+1] - 1 }

よくわかりません。どうして？

P.S

まだまだ面白性質あります。よくわからんけど

数式書くのむずかしいぜ。はてな