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と足し算の間に都合のいい性質など考えようもないが、ビットごと …

ジョギングした。2.5km。おととい腕立て伏せをした影響が残っているのか、肩が痛くなった。 今日解いた競プロの問題。 ARC148-C: ある1頂点のコインだけを裏返す方法を考えると、その頂点のボタンとその頂点の全ての子 …

今日解いた競プロの問題。 ARC140-C: 自力AC。実装はややこしいが方針は気付けば簡単だった。 まず、Aの長さはN-1なので嬉しさの上界は自明にN-1である。検討してみると、条件次第ではこれが達成できるのでその場合 …

今日解いた競プロの問題。 ARC145-C: なんとか自力AC。かなり厳しかった。 まず、スコアの最大値Mが実際どうなるのかを考えてみる。2つの長さNの数列A,Bがあり、1～2Nまでの値が1つずつ含まれている。数列や集合 …