あああああ

オタク & 競プロ

Increment Decrement (AGC049-E) 別解

問題

atcoder.jp

 

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

 

 

解法

01で解くのをNK回すれば良いです。

 

K = 1のときの最適化問題に戻ってdpを考えると、

状態A : 1のときにコスト1かかり、0のときにコスト0かかる。

状態B : 0のときにコスト1かかり、1のときにコスト0かかる。この状態にするときにコストCかかる。

をうまく行き来するのが最適なので、

dp[i][f] = i 要素見て今の状態が f のときの最小コスト、というdpで解けます。

状態Bは操作2で区間+1をしたあとに操作1で1点-1をするのに対応しています。

 

dp[i][0]の値とdp[i][1]の値をキーにすることで(Nより大きくなったらNとして良い)最小コストが0,1,...になる数列の数を数えられます。

 

計算量はO(NK(NK+N^3)) です。

 

提出

atcoder.jp

競プロ コンテスト(海外含む) まとめ

独断と偏見で、今ぼくが参加している定期コンテストにおすすめ度をつけます。(2024年3月時点)

橙、赤を目指していく人向けの点数付けにしていますが、AGCとUniversal Cup以外は序盤は比較的易しいので興味があったら好きなだけ参加していっていいと思います。

全部日本時間(UTC+9)です。

 

 

要約

ざっくり並べると、

必須級 AGC,ARC,CF Div.1級,UCup

結構おすすめ DMOJ,CF Div.2,yukicoder,solved.ac

まあまあ ECR,TLX,codechef Starters

普通 ABC,Div.3

まあ SRM

 

AtCoder

 

AtCoder Grand Contest (AGC)
  • 年6回程度 日曜多め
  • 21:00〜
  • 150〜180minが多い
  • 言わずと知れた超超高難易度コンテスト
  • おすすめ度 10

 

AtCoder Regular Contest (ARC)
  • 月2回程度 日曜多め
  • 21:00〜
  • 120min
  • レート上限があるコンテストの中では最も難しく面白いと感じる。
  • おすすめ度 9

 

AtCoder Beginner Contest (ABC)
  • 週1回 土曜多め
  • 21:00〜
  • 100min
  • 賞金狙い&典型の練習に
  • おすすめ度 3 (ボスの難易度にもよる)

 

Codeforces

 

Div.1/combined
  • 月2回程度 最近は土曜が多い印象
  • writerの地域によるがだいたい23:35〜
  • 120〜180min
  • AtCoder以外でどれに出るべきかランキング殿堂入り レート変動が大きすぎることがよく欠点として挙げられているが、真面目に十分な回数でればだいたい実力わかるし、highestとaverageそれぞれで実力変化を測ることは可能だと思う。
  • おすすめ度 10

 

Div.2
  • 月2回程度
  • writerの地域によるがだいたい23:35〜
  • 120minが多い
  • 序盤ギャグ寄り 実装実装というイメージは過去のもので、実はボス問はad-hocな良問も多い。
  • おすすめ度 6

 

Educational Codeforces Round (ECR)
  • 月2回程度
  • 23:35〜
  • 120min
  • 教育と呼ばれているが、最近はそうでもない気がする。後半で、あるアルゴリズムを使います系は多いかもしれない。
  • おすすめ度 5

 

Div.3
  • 月2回程度
  • 23:35〜
  • 135min
  • 僕はほとんど出ていないが、ABC早解きの練習にいいかもしれない。
  • これより簡単なDiv.4というのも一応ある。
  • おすすめ度 2

 

topcoder

 

Single Round Match (SRM)
  • 年8回程度
  • 色々(10:00〜や25:00〜が多い)
  • 75+5+15min
  • chal(hack)をするための時間が設けられているのが特徴で、やってみると結構楽しめる可能性が。最近はジャッジ側のバグも多く、all ratedなのに青diff以下ばっかり出るが、速度を強く意識させられる点数システムなので、完全に出る意味がないわけではない、と思いたい。rngさんadmin時代の過去問はよくオススメされている。
  • おすすめ度 1

 

yukicoder

 

  • 毎週金曜
  • 21:20〜
  • 120〜180min
  • 昔は玉石混合という印象だったが、最近はまともにテストしてくれる人が増えていそうで、微妙な回だったとしても理由は典型すぎといった形で大きな問題はなく、全体的に質はいい。ここで何セットか書いた後にARC/AGCのwriterになる人も増えてきていて、また、あまり見ない中高難易度典型がここで練習できることも多く、置いていかれないためには有効?
  • おすすめ度 7

 

codechef (インド)

 

Cook-Off,Lunchtime
  • 停止中
  • ICPCルール,OIルール
  • adminがUm_nik,anton,244mhqの頃の問題は非常に評判が良かったという記憶があるため、vjudgeなどを用いての演習にはよさそう(2020か2021〜?)。現在は問題の枯渇により開かれていない。
  • おすすめ度 9

 

Starters
  • 年6回程度(星6以下だとほぼ毎週),水曜
  • 23:30〜
  • 120min
  • rated範囲が毎回変わる。all ratedの頻度は年に6度ぐらいで、星6以下(AtCoder2300ぐらい?)ratedが大半。僕はall ratedにだけ出ているが、質はそこそこ。rated範囲の告知が前日や当日なことが多いので、チェックが大変。
  • おすすめ度 4

 

DMOJ

 

  • 頻度 不定期(年8ぐらい)
  • 金昼〜火昼の好きな時間に3時間選んで行うのが多い
  • OIルールのため、順位表情報がない
  • rated範囲が細かい。〜3000rated(AtCoder2900ぐらい?)の頻度を上に書いた。allになると2,3回減りそう。インタラクティブやパズルがほぼ毎回出るが、しっかりと木の実装させたり数え上げだったりも出て、ジャンル広め?順位表が見られないコンテストは珍しく、やってみると予想以上にうまくいかないことが多い。週末の好きなタイミングでできるのは嬉しい。
  • おすすめ度 8(順位表hidden & 時間選べる点で+1)

 

TLX (TOKI) (インドネシア)

 

  • 年6回程度 ほぼ土日
  • 21:00〜23:00スタートが多い
  • 120〜150min
  • 序盤で大胆予想が必要(?)な問題が多い。質は少し劣るが、ARCに近いんじゃないかと思っている。
  • おすすめ度 6

 

solved.ac

 

  • 最近できたサイトなのでまだ色々謎
  • 土日の昼スタートが多い
  • 180〜300min
  • 韓国のサイトで、英語問題文が提供されてたりされてなかったり、rated範囲も毎回変わる。ソロで300minのICPCルールのratedができることが特長でもある。ボス問は結構骨のある問題という印象がある。
  • 色々有志コンとかもratedでやっていそうだが、solved.ac Grand Arena #n というタイトルのが最も格が高そう。
  • おすすめ度 7

 

Universal Cup (UC) (UCup)

 

  • ほぼ毎週
  • 土曜 9,11,14,17,20,22,24,27時の好きな時間から開始可能(ABCやCFと被ることが多く、日本人には14時が最も人気なイメージ)
  • 300min
  • https://codeforces.com/blog/entry/118679
  • 中国のトップ層が運営していて、中国のICPC練習用or本番セットや、Petrozavodskなどのcampで使われたセットで競う。基本的には3人チームを組んで参加する。難易度は非常に高い(意欲のある黄か橙以上向け?)。
  • https://qoj.ac/contests ここに全てのセットが上がっている。
  • おすすめ度 10

 

usaco

 

  • 年4回
  • 300min
  • まともとは聞くが、OIルール(コピペ検索禁止?)が強制っぽいのが嫌で手を出していない。参加した強い人からの情報を求めています。
  • おすすめ度 ?

 

Project Euler

 

  • 休暇期間以外は週1回1問出題(たまに2問)
  • 出題時刻は土日のどこか24hを切り取って周期8で3hずつずれていってた記憶だが、正確な時刻はわからず(わかったら書きます)
  • 時間無制限だが、上位100人はランキングに名前が載る
  • レーティングはないが、直近10問のうち成績のよかった5問を切り取ったスコアでランキングがつくほか、過去問を解いた数でもランキングのようなものが見られる。
  • 難易度は、ABC-Eクラスからトップ層でも1日かかる問題まで幅広い
  • ジャンルは相当数学寄りだが、数え上げやゲームや数論など競プロ視点で勉強になる問題も多い。
  • おすすめ度 ?

 

その他

 

  • AtCoderやAOJで開かれる有志コン
  • JOIミラー
  • CFで開かれるICPCミラー
  • CFブログで告知されてる、準備陣にLGMがいたりIGMたくさんだったりする謎コンテスト

もおすすめです。

 

https://clist.by/#

このサイトを毎日見てればコンテスト逃すことは99%なくなると思うのでそうするのがいいです。

 

最後に

これにちゃんと出るとコンテストだけで平均1日2時間近くになるらしい

充実したコンテストライフを!

AGC021-F Trinity

金diff!

 

問題

atcoder.jp

 

概要

日本語なので省略

 

公式解説より見通しがいい感じの解法になった気がするので書きます

 

 

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

ネタバレ避け

 

 

 

解法

列の組(A,B,C)に対応する黒マスの塗り方は、AでもBでもCでも関わらないような黒マスを作らないようにすれば一意に決まります。

よって、次のようなマスの塗り方を数えれば良いです。

 

全ての黒マスについて、以下の条件1,2,3のいずれかが成立する。

1. 自分より左に黒マスがない。

2. 自分より上に黒マスがない。

3. 自分より下に黒マスがない。

 

右の列から黒マスの配置を決めていくことにします。

このとき、条件2,3のいずれにも関わっていない黒マス(つまり、一番上でも一番下でもないもの)は、条件1を満たしている必要があるため、それ以降(それより左の列)はその行には置けない、とすることになります。

 

dp[i][j] = 右 i 列を見て、 j 行はもう黒マスを置くことができない、とした通り数とします。

 

遷移を考えます。

右から i 列目に置く黒マスの個数で場合分けします。

 

0個の場合

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

 

1個の場合

これは、j 行以外ならどこにでも置けて、黒マスを置くことができない行の数は変わりません。

dp[i+1][j] += dp[i][j] * (H-j)

 

2個以上の場合

これも、j 行以外ならどこにでも置けて、新たに j - 2 行が黒マスを置くことができない行になります。なぜなら、一番上と一番下以外の j - 2 個は条件1を満たすようにするしかないからです。

dp[i+1][j+k-2] += dp[i][j] * (H-j) C k

 

これをそのまま実装すると、O(N^2M)で部分点が取れます。

あとは畳み込みで高速化するとO(NMlogN)になり、満点が取れます。

 

実装

atcoder.jp

今年もおつかれ

大学に復帰してからは、そこそこ遠い通学に大量の1限に実験&実験レポートで、今までで最も長く感じられる大変な一年だった。

そんな中で一応耐えられた要因となったものを挙げる。

 

・競プロ

〇〇を理由にしてコンテスト出ないのはカスwとか言ってた手前全部出た、まあそもそも全部出たいからあんまり関係ないけど。

平日を乗り越えたらUniversal CupやCF Div.1や賞金ABCのどれかがだいたい待ってることは大きかった。ただ、大学のせいなのか今年は伸びがイマイチだったのは許せぬ。徹夜して大学に行くのにも耐性がついてきたからもうちょい練習したい。

シンプルに問題の面白さはあるが、自分の努力パートを1つのことに捧げているというのは言い訳ができなくて清々しい気分であり、一方息抜きのオタクパートでは実力要素のない快を得られていて、ちょうどいいバランスになっていると思う。

 

・虹ヶ咲

曲を行き帰りの電車内でよく聴いていた。

ライブにもたくさん行った。

A・ZU・NA Day2

QU4RTZ 両日

にじたび 東京 Day2昼

にじたび 福岡 Day2昼夜

異次元フェス 両日

虹6th 愛知 両日

後述するが、福岡と愛知は実験の後に遠征して帰ってきて翌日も大学、という感じのスケジュールだった。だが、食事目的で行ってみたい場所だったのもあり、それも含めてとても楽しかった。

 

・オタク

漫画

今年はたくさん読んだ気がする。アオのハコ、マンガ家さんとアシスタントさんと、が特に面白かった。

 

ラノベ

ココロコネクトが面白かった。

 

美少女ゲーム

はつゆきさくらが面白かった、これは自分の触れた作品の中でもトップクラスに好き。

 

Hesitation Snow、夜明けのベルが鳴る、Tragic Drops、わちゅごなどぅー、咬福論、などが好きです。最近プレイした補正はあるだろうけど、前2つは特に抜けてるかも。

 

・飯

これは公式と自分の撮ったやつの比較画像、すごいw

大学にキッチンカーが来ていて、そこのメニューを全制覇した。ほんとにキッチンカーの新作を楽しみに行ってるようなものだったので...

A火のパエリアと、D月のビーフステーキがおすすめ

まじで体重増えてきてやばいが、運動する気もなくて、食事減らすと日常の何が楽しいの?ってなるので詰んでる。

チェーンだと、蒙古タンメン中本、クアアイナは美味しくて複数回行った。

 

・旅行

福岡と名古屋に行った。

まあライブの遠征が目的だったので、あんまり観光はしてなくて、関門トンネルを歩いたり、東山動植物園に行ったり、大須を散策したり、ぐらい。

飯はいい感じで、小倉のうなぎの店、鉄なべ餃子、もつ鍋、博多ラーメン、かしわ飯の駅弁、焼きとんかつ、名古屋コーチン手羽先、きしめん味噌カツ台湾ラーメン、モーニング、味噌煮込みうどん、ベトコンラーメンを食べた。

腹の調子が悪くて焼きカレーが食べられなかったのが後悔。

ここまでだと完璧に思えるが、普段かなりの夜型のせいで、朝から出かけてチェックインも早朝、3食食べるには昼に観光するしかない、というのはかなりストレスで、そこが大きくマイナスポイントになってしまい、来年もするかは未定。コンテストと被らないお祈りもだるい。

 

・人付き合い

学科で話す人ができたのは正直ドロップアウトしないという点で大きかった。馴れ合いはカスwとか言っているのにそれで助かってしまうのは皮肉なものである。

昔からの友人とはよく食事で集まり、今年はキャンプに行くなどできてよかった。だんだんと歳をとってきて現状報告を本音でできる人が少なくなってきているのでこれからも大事にしたい。

 

・抱負

周りの人間を見て焦り、とかは今のところないし、もうずれすぎて感覚バグってきてるのでそれを活かしてこれからも流されずやりたいことをやっていきたい。

 

おわり

 

2023年まとめ

続きrubikun.hatenablog.jp

 

レート

AtCoder 2841 → 2741 (-100) (highest 2841) 笑

Codeforces 2941 → 2730 (-211) (highest 3033) 笑

topcoder 2899 → 3154 (+255) (highest 3170)

codechef 2839 → 2903 (+64) (highest 2903)

DMOJ 2780 → 2911 (+131) (highest 2917)

toki 2646 → 2717 (+71) (highest 2746)

 

精進

AtCoder 4334 → 5758 (+1424) (3位→2位)

RPS 1050600 → 1353150 (+302550) (7位→4位)

Codeforces 2468 → 3028 (+560)

AOJ 762 → 763 (+1)

yukicoder 175 → 319 (+144)

Library Checker 14 → 28 (+14)

CodeChef 150 → 193 (+43)

topcoder 175 → 194 (+19)

Sum 8077 → 10283 (+2206)

AOJ-ICPC 257750→257750 (0) (5位→5位)

Project Euler 350 → 352 (世界736位,日本44位)

(OtherにADTが720問入っている)

感想

練習量キープしていれば自然にレート上がるだろうと思っていたが、LGMタッチしてからは学生コン入賞したぐらいでかなり終わっていた

低難易度はUCup序盤とDiv.2で足りてる感じがしてて、典型の速度はABCで良くて、中難易度が足りないのかなという感じなので引き続き練習、高難易度はあと266問差を詰める間に勝手にやることになりそう

highestに戻すのとAC数1位が目標

整数三分探索の罠

TLで見たから書いておく

C++の除算の話です

 

[l,r) のときに x = (l + l + r) / 3, y = (l + r + r) / 3 として f(x) と f(y) を比較して幅を 2/3 にする、ってのがよく使われている実装だと思います。

 

(例)

[1,5)のときに x = (1 + 1 + 5) / 3 = 2 , y = (1 + 5 + 5) / 3 = 3

 

(本題)

[-2,2)のときに同じことをやると...?

x = (-2 + -2 + 2) / 3 = 0 , y = (-2 + 2 + 2) / 3 = 0

 

 

二分探索だとこれでは死なないので気づきにくいですね