週記(3/15~3/21)
そろそろ今週の週記を書き始めるか(土曜日の17時)
3/15
何も覚えていないが、slope trick の勉強はしていたはず。
それはそうとして1日の内容が薄過ぎない?
3/16
夕方は少し用があって外出をしていた。
夜はAOJ-ICPCの450点問題をやっていた。
3/17
急に生活習慣が改善して8時前に起床した。
ついついICPCの順位表を眺めていたら午前中が消滅していた。
その後、通話を繋ぎながらYes/Noまで見てしまったので夕方まで消滅した。
Codeforces Round #708 (Div. 2)
途中サイトが重くてまともに問題ページが開けない時間帯があったはずなのに、現時点ではunratedにする理由は無いと堂々とアナウンスしていて面白かった(結局15分延長決めた後にunratedになったらしい)。
Currently, we don't see reasons to make the round unrated(迫真)
— かっつ (@_KKT89) 2021年3月17日
topcoderの謎コンに出るため途中撤退。解けていない2問について、E2はまだ何とかなりそうな雰囲気があるが、コンテスト中にも少し考えていたDはまだ分かっていない。
2021 HF Prelim
謎コン。Easy,Medは流石にOKという感じで、Hardは普通に分からなかった。終了後のTLを見るとダブリングで頑張る問題らしい。
1859→1883(+24) このコンテストでhighest更新していいのか…
3/18
この日は先週の5hのupsolveをしていた。
今日から大学の履修登録が始まっていたのでそれもさっさと済ませておいた。
親と割と真面目な話をして、将来についてそろそろ真剣に目を向けていかないとなぁという気持ちになっていた。競技プログラミングに傾倒出来る時間を大切にしていきたい。
Educational Codeforces Round 106 (Rated for Div. 2)
Cまでは問題無し。D問題も本番では解法はすぐに辿り着けてpretestを通せたのだが、hackで強いケースが次々と投げこまれ、システムテストではTLEしてしまった。
この日記を書いてる途中で、FastIO + #pragma GCC optimize("Ofast")
の書き換えを行い、1731ms/2000ms で無事AC。力こそパワー。
E問題は基本的なDPの問題なのだが、それぞれ最後に使ったindexに加え最後に使ったアルファベットの種類(×26)も状態として持とうとしてMLE解消に苦しんでいた。
冷静になると、最後に使った文字列がどちらかだけを記憶しておけば26種類も状態を持つ必要がない。本番では配列を使いまわすように丁寧に書き換えて通した。
3/19
SRM486 久々にバチャ参加
- Easy
- 取りうる値は少ないので適当にBFSすればOK
- Med
- 座圧して上界と下界を持ったメモ化再帰
- 制約が小さいので雑をしても通る
腹痛に苦しみながらバチャをやり、横目でチラチラ明徳vs仙台育英の試合を見ていた記憶がある。
SRM802 20時からの人権時間SRM
- Easy
- 期待値が出て焦ったが比較的早く通せたと思う
- 見た瞬間書き始められるようになるまでは少し遠いなぁという感じ
- Med
- 全探索で良さそうだが厳しめのTL設定
- 上手く集合を列挙する方法が分からず、ひたすら愚直DFSの高速化を図っていたがダメだった
- 苦心してた甲斐あり、chalでは部屋の愚直DFSを3つ墜とせた
- 1883→1918(+35) Highest
眠かったので遅刻参戦。面白そうな見た目をしているE問題を考えることにする。
到達可能の条件を考慮するとグラフ全体が1つの強連結成分に属していないとダメ。次に色の条件を考えると明らかに二部グラフではダメで、加えて単一のサイクルを形成するような場合(N==M)もダメということが分かる。逆にこれ以外の場合は解が存在する。
本番は奇数長のサイクル2本を発見することに拘ってしまったが、1本で十分なケースも存在するのでこれは嘘。構築パートはまだ考え中。
ところでこの問題のジャッジはどう書くのだろうかと疑問に思っていたら、(出題当時は)不完全なジャッジだったらしい。熨斗袋さんがツイートしていたジャッジ方法について後で考えてみる(ToDo)。
E は dp[v][i] = 頂点 0 から頂点 v まで、R-B=i で行けるか?というのを -3N <= i <= 3N くらいの範囲で計算して、dp[0][i] = true なる i について gcd を取るとジャッジできる気がしました。
— 熨斗袋 (@noshi91) 2021年3月19日
3/20
午前中はせっせと解説ブログを書いていた(これ)
先日、ツバサさんと通話していた時に話題に上がっていた問題を考えることにした。
考えているうちにうっかり昼寝してしまったが、結局足し合わせる項の数を固定して下の桁からメモ化再帰をする方針で十分そうとなる。解の復元にやや時間をかけてしまったが、そこまで苦戦せず通せたので良かった。
久しぶりにAtCoder Problemsを覗いて手の出せそうな黄difをちまちま埋めるなどしていた。
2200ms かかってるけど通った
— りあん (@rian_tkb) 2021年3月20日
__builtin_popcount が遅いという話に出くわして、#pragma GCC target("popcnt")
をつけたら 4 倍くらい速くなったhttps://t.co/UrDHuuu9H5
__builtin_popcount
の高速化に #pragma GCC target("popcnt")
が効くらしい。
また、$ 2^{15} $ 未満の __builtin_popcount
を前計算しておいて、bitの立ってる数を高速に求めるテクニック( $ 2 ^ {30}$ 未満であれば前半と後半に分ければ前計算が活かせる)を丁度今日見かけていて、こちらもなるほどなぁとなった。
最近この手の処理が絡む問題の定数倍高速化で苦しまされる機会が二度程あって、しんどい気持ちになっていた。学んだこととしては、std::bitset
のランダムアクセスは遅い。TL/計算量がキツイ問題が出題されるコンテストに出ない!(素振り)
AOJ-ICPC 1問消化して寝た。
3/21
SRM488
- Easy
- 流石にこれぐらいの期待値問題はOK
- と思ったらメモ化再帰のメモ化忘れでTLE 良くないね
- Med
- かなり時間がかかった
- 2つの文字列ではみ出てるところを固定すると前計算が効く形になるので解ける
Medの実装に手間取っていたら夕方になっていて、夕食を済ませると3連コンテスト前の微妙な時間になっていた。
- 序盤の速度からダメで遅解き3完 2041→2006(-35)
- Aは最初誤読していて鳩の巣原理ですね〜と実装していたらサンプル2で真顔になった
- Bも難しい 眺めてると最小値を0に固定しても解に影響を及ぼさないことが分かる
- Cは面白いと思う 気付けば一発
- Eみたいな見た目のを解けるようになりたいね
Codeforces Round #709 (Div. 1)
- C解けないのダメ… 2124→2116(-8)
- ABの速度で何とか軽傷で済んだけどそろそろ紫が見えてきているので踏ん張りたい
- Div. 1で全体15位取りました(なんで???) 2062→2215(+153)
- 高度な考察力が求められず、実装してくださいみたいな問題セットだとたまに良い結果が出せるのかもしれない
今週を振り返って
可もなく不可もなく