/ 最近 .rdf 追記 編集 設定 本棚

脳log[20210624]



2021年06月24日 (木) 今日も競プロ典型 90 問。■「073 - We Need Both a and b(★5)」 すごく難しいです。解説を読んでも難しいです。青 diff 後半だった「ARC112-C DFS Game」は(時間をかけて)解けても、これはまだ。解説を読めばプログラムの型はできていたことがわかる。大きなミスは、あるノードを根とする部分木について考えるとき、「単色になる場合」と「二色になる場合」を数えるにあたって、切り捨てる場合があることに気がつかなくて(解説のこの部分「辺(pos,bi)を削除するとき頂点 bi を含む連結成分が 'a', 'b' 両方含む必要がある一方、削除しないとき 'a' しか含まないから」)、必ず単色・二色のどちらかに振り分けようとしていたこと。一応 AC>#23696813 (同じ内容。あ、concat と << でスタックに二重に積んでる)■「074 - ABC String 2(★6)」 前日より★が多いけど、これは★3つくらいのあっさりさで解けた。「この桁の変化は(逆向きだけど)すごく見覚えがあるぞ」「だけど繰り下がりに伴う変化だけちょっと違うぞ」というあたりから。.tr.to_i+.tr.to_i (@2021-06-28 .to_i 一発(相当)で計算できるこんな言語もあるらしい。「2001を2進数で解釈するというのは通常だと意味が通らないが、dcにおいては構わず2×2^3が使われる」)■今日はこの他に取りこぼしていた「045 - Simple Grouping(★6)」を Ruby で通しておいた。組み合わせの総当たりが bitDP でできるというのは初めて知った。Avoid War がまだ通せないとは 20210622 で書いたけど、そのときに覚えた部分集合の列挙をビット演算で行う方法(蟻本に載っていた。144 ページ)がさっそく使えた。1つのケースだけ 20 秒くらいかかって TLE になるので、その場合だけ別の方法で答えを出すなど>#23710778 (1087 ms / 同じ内容)。□わずかな時間を削るためにいろいろと猪口才なことをしている。配列の配列を作るときに長さ14で2^{15}個のインスタンスがいいか長さ2^{15}で14個のインスタンスがいいかとか。2点間距離をメモした D 配列がそのまま DP 配列(E)の初期値であるとか(だから本当は3ビット以上立っている数に限って列挙したい)、DP 配列のその他の初期値が最大値ではなく 0 でいいとか、それによって中間ループを K 回回さないで済んでるとか。ループの中で最初から最後まで使われている d 変数の初期化が実は1回だけですよとか。最内ループの C if A && B が多少冗長ではあるがコストの順に並んでいて総合的には得するだとか(少なくともローカルでは)。しかし、点を一列に並べて端っこから2番目の点を無き者にしてループの指数を1減らす試みは失敗した。