今日解いた競プロの問題。 いろはちゃんコンテストDay1-J: 超がんばって力業で解いた。 Nが偶数の時: $n=N/2$、$S=A_1+…+A_n$と置いて超がんばって計算すると、転倒数は$2S(n-S)$ …

レポートがあるのに、現実逃避して授業受けて現実逃避して一日が終わった。 やりたいことをやっていられずやらなければいけないことが手につかないデッドロックで精神があれになっている。 今日摂取したコンテンツ。 ChatGPTが …

今日解いた競プロの問題。 ABC237-F: 解説AC。といいつつ、解説にはほぼdpテーブルの形しか書いてなかったので、自分で考察し直した。 まず簡単な場合として、LISが3ではなく1の数列の個数を数えることを考える。左 …

ABC281に参加した。 A: やるだけ B: がんばる C: TをAの総和で剰余をとった上で順に見ていく D: dp[i][j][k]:=i番目まで見てj個採用してmod Dがkであるような和の最大値 E: mapに値 …

レポートに追われて半徹夜をした。今もレポートに追われている。助けてくれ。 E・F・ベンスン「塔の中の部屋」を読んだ。ホラーシーンの盛り上げ方をめちゃくちゃ分かっている。文字媒体なのに光景がありありと浮かんだ。 読み終わっ …

今日解いた競プロの問題。 いろはちゃんコンテストDay1-I: リスの状態は(今いる木, 最後に通った枝の隙間の大きさ)で表される。これは$O(NM)$あるいは$O(N\max C)$になってしまいそうだが、ちょっと考え …

昨夜日付が変わる前に寝て、10:30くらいに起きた。起きる時間を固定しないと結局ずるずると夜更かししてしまう気がするので、起きる時間を固定した方が良い。 明後日までのレポートなどがあり、夜更かししてしまった。うーん、良く …

今日解いた競プロの問題。 ABC165-F: LISはセグ木を使って$O(N\log N)$で求められるが、当然全ての頂点について$O(N\log N)$かければTLEする。 LISを求めるアルゴリズムの中身を考えると、 …

今日解いた競プロの問題。 ABC229-F: 観覧車みたいな形のグラフを切って二部グラフにしろという問題。 最初は各辺を切っていく方針で考えていたが、「頂点0, i, i+1の為す三角形のどこかを切る」だけでは必ずしも二 …

なんかぷよぷよの練習をしていたら日が落ちていた。俺はなぜこんな時間を… 今日解いた競プロの問題。 CPSCO2019-Session3-E: XORと足し算の間に都合のいい性質など考えようもないが、ビットごと …