ABC197に出た。久しぶりの全完。黄パフォだった。しかも個人的にかなり好きな問題セットだったので楽しかった。
Aはやるだけ。
Bは普通に上下左右にそれぞれ追っていけばいいのだが、重複カウントとかに関する細かい正当性を考えるのが面倒くさくなって、カウントするのではなくsetに座標を記録した。ちょっと考えれば分かる程度なので要るのかこれという気はする。問題の本質と全然関係ないけど、XがHの範囲でYがWの範囲なの本当にやめてほしい。自分にはどうしてもXが横軸でYが縦軸、かつ座標を示す際は(x, y)の順という感覚が拭えない。入力部分で工夫して何とかした。
Cはbit全探索。Nが小さいことに一瞬気付かなくて焦った。塗分け($2^N$)で区間分割を表して全探索したのだが、解説を見たらN-1箇所の境界に仕切りを入れるか入れないか($2^{N-1}$)を全探索すれば良いと言うことでなるほどと思った。まあ2倍しか違わないし良いでしょ…
Dはやるだけ。シンプルな幾何問題は好きだ。難しいのだと色々正当性を考える必要がある。今回atanするときに$x_0=x_{\frac{N}{2}}$だと0除算になるんじゃないの…という危惧が一瞬頭をよぎったが、ゲーム開発でもおなじみのみんなの友達atan2(y, x)によって粉砕された。というかatan2ってc++標準だったんだ？
Eはすぐに方針が経ったが、ちょっと細かい部分を詰めるのに苦労した。どうせ$C_i$が同じボールはいっぺんに全て取らないといけないのと、右端と左端の間にあるボールは途中で見逃す理由がないので、$C_i$が同じボールの内の最右→最左と最左→最右のどっちをやるか、という話になる。$C_i$が同じものでまとめて、ダイクストラでACした。
(最右→最左)→(最右→最左)、(最左→最右)→(最右→最左)、(最右→最左)→(最左→最右)、(最左→最右)→(最左→最右)の4パターンを考えなければいけないので面倒くさかった。解説見たらDPだったし、もうちょっといい実装が出来たと思う。
Fはとても気持ちよかった。最初全く方針が思いつかないのでサンプルケースで実験をしてみる。
回文を作るので、両端から始まって同じ文字の辺がある場合のみ遷移しなければならない。(空文字列, 1, 8)→(“a”, 2, 7)→(“ab”, 3, 6)という感じ。で、途中で「あれ？これルールに従って遷移すれば座標さえ持てば良くて、文字列持つ必要なくね？」と気付く。ここがいっちばん気持ちよかった！
で、そこに気付けば頂点の組を頂点としてダイクストラして優勝。お疲れさまでした。
元のグラフにおける1つの頂点を、状態で複数の頂点に分けるようなダイクストラ応用というのはやったことがあるけど(ex.ABC164-E)、直積を持つというのはやったことが無かったのですごく面白かった。
ちなみにダイクストラではなくBFSで十分だったらしい。よく考えたらそれはそう。あと、自分は$(1,N)\rightarrow(i,i), 1\leq i\leq N$と$(1,N)\rightarrow (a_i,b_i), 1\leq i\leq M$の最短距離を調べたけど、$(1,N)\rightarrow (N,1)$の最短距離を見ればいいというのをながたかなさんが言っていた。なるほど確かに。これは面白い。
このはカレンダーをめくってなかったのでちゃんと3月にした。
着物めちゃめちゃかわいいです本当にありがとうございました。表情もこのはちゃんにしては珍しいかも？
学校なのも雰囲気が良い。好き。ただ学校で着物なのはどういうシチュエーションなのか(野暮なツッコミ)
鬼滅の刃の5巻を読んだ。件のサイコロステーキ先輩が出てきてオッてなって、目にもとまらぬスピード感であっと言う間におっ死んで、予想していた早さのはるか上をゆうゆうと超えていった。イヌーですらもうちょっと健闘してたと思う。本当に敵の手の内見せるためだけに不自然に表れて順当に死んでいった。すごい。
鬼家族の真実これなかなか好きだな。特に母(役)の鬼。女の子が、ひどい目に遭うのは、かわいいので。自称十二鬼月の弟君もいい。経験の結果性格がバグったキャラは好き。
胡蝶しのぶ、抜けてる天然なんだか、あれ自分なんかやっちゃいました系の実は全て見通してる強キャラなのか判別が付かない。複合？新しいな…
Categories: 未分類