あああああ

オタク & 競プロ

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

 

 

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

ARC140-F ABS Permutation (Count ver.) やや別解

問題

https://atcoder.jp/contests/arc140/tasks/arc140_f

 

解説

 

公式解説では [x^N] (x+2x^2+2x^3+...)^K を 1<=K<=N について求めよというパートが出てきてここでダブリングをしていますが、別の方法を紹介します。

 

Kを固定してみると、求めたい値は

[x^(N-K)] (1+2x+2x^2+...)^K

= [x^(N-K)] ( (1+x) / (1-x) )^K

= [x^(N-K)] (2/(1-x)-1)^K

となり、ここを二項定理でバラして K - i = j とすると、

(分子) = 2^i * (-1)^j  * (N-j-1)! * (i+j)!

(分母) = (N-(i+j))! * (i-1)! * i! * j!

になって畳み込めるので、そうすると高速になります。

 

実装 (fastest)

https://atcoder.jp/contests/arc140/submissions/43458503

 

質問

[x^N] f(x)^K を K=1,2,...,について求める系って一般的ななんかうまいやり方ありますか?

ARC122-F Domination 別解

問題

atcoder.jp

 

解法

 

赤い石は RX_1 < RX_2 < ... < RX_N , RY_1 > RY_2 > ... > RY_N となっているとして良いです。

このとき、各青い石がカバーするのは区間になります。

 

青い石を1個ずつ見ていきます。(石 t と呼ぶ)

 

パターン1

x座標もy座標も自分より大きいような赤い石がない場合

この場合は、既にいくつか(0個の場合もある)の赤い石をカバーしていて、y座標を増やすと区間の左端が左へ、x座標を増やすと区間の右端が右へ進んでいき、独立に考えることができます。

 

パターン2

x座標もy座標も自分より大きいような赤い石がある場合

そのような赤い石の集合をSとします。

この場合は、初期時点では赤い石を1つもカバーしていません。

石 t が赤い石を1個以上カバーするように操作するのが最適なら、石 t はSを全てカバーするとして良いことがいえます。

 

証明: 適当にカバーしている区間を縮めて、全ての赤い石のカバーされる回数がちょうどKになるようにしておく。a, a+1 をSの要素として、石 t がカバーする区間が [l , a] という解が最適だとする。このとき、a+1 はカバーしているが a はカバーしていないような石が存在するが、その石が追加で [l , a] もカバーするようにして石 t は 1 つもカバーしないようにしても解が悪化することはない。(証明終わり)

 

このことを利用すると、だいたいパターン1と同様に考えられるようになります。

Sの要素のうち x 最大のものを s としたとき、青い石 t を 赤い石 s のところまで移動させるコストを最初に払うと、石 s での更新処理を適切に行うことでパターン1のように扱えます。

 

最後に、ここからどう解くかを考えます。

dp[i][a][b] = i 番目の赤い石までは条件を満たしていて、y座標を増やしてカバーするのに使う青い石の借りが a 個あり、x座標を増やしてカバーするのに使える青い石が b 個あるときの最小コスト と定義して更新タイミングを頑張ると N=M として O(K^3 N + NlogN) で解くことができました。

(aを増やす、bを増やす、a+b+(最初からカバーされている個数) >=K かをチェック、aを減らす、bを減らす、パターン2の処理、の順)でやったのですが、スライド最小値を使わないで O(K^4 N + NlogN) にした方が速かった

 

提出

https://atcoder.jp/contests/arc122/submissions/41292048