Vulkan入門を書き進めた。zolaのディレクトリ構造の整理がやっと終わったので内容に集中できる。プッシュ定数とシェーダアルゴリズム周りはまあいいのだが、ステージングバッファの節を真面目に書くやる気が出ん。
久しぶりに夕飯に外食。レストランで割とがっつり肉を食べた。なかなか満足した。高級レストランという訳ではないので絶品料理みたいなやつではないが、肉は肉というだけで全てを回復させるパワーがある。
ARC156に出た。Aに時間かけすぎた。
A: ちょっと考察すると分かるが、表のコインの数および裏のコインの数はどちらも2個ずつしか変わらない。従って表のコインの枚数が奇数なら不可能。またコーナーケースとしてn=3のとき、両端のコインの内片方だけが表の場合と真ん中のコインが表の場合に不可能。それ以外ならば全て可能。
残ったのは表のコインが偶数である場合だけだが、これは出来るだけ表のコイン同士を合わせてやりたい。そこで、表のコインを左半分と右半分に分ける。そして左半分の表コインと右半分の表コインをマッチングさせていく。これによって表コインの枚数/2回で全て裏にでき、最適となる。これは表コインが4枚以上ならば必ず可能である。マッチングさせるコインは間に1枚以上コインが挟まっている必要があるが、4枚以上ならば順番に合わせていけば必ず間に1枚以上挟まるからだ。問題は表コインが2枚だけかつ隣接している場合である。
これは適当な裏コインを仲介することで2回で行ける。ただし1枚以上間に挟んだ位置にある裏コインでなければならないので、n=4の0110がコーナーケースとなる。この場合は3回で可能。
地味にコーナーケースの多い問題だった。コーナーケースの詰めはまあ苦手ではないのだが、半分に分けてマッチングさせるのを思いつくのに大幅に時間を費やしてしまった。悔しい。
B: 任意に集合をとってそのmexを追加できるということは、順に下から数を追加していけばある数以下の任意の数を追加できるようになっていくということになる。なので追加する数の最大で場合分けすれば良い。また求めるのは「構成可能な集合のパターン数」であり、数字を追加するだけで削除する操作はないので、単純に各整数ごとにいくつ追加するかを考えればよい。
追加する数の最大をmとすると、m未満の全ての非負整数が書かれた状態にした上でmを書く必要がある。これに必要な操作回数は、m未満の整数でAに含まれているものの数をmから引き、mを書く分1足せばよい。必要な操作回数をKから引いた分の操作回数は自由に使えるので、これをpとすると${m+1}H_p$通りの多重集合が構成できる。これを各mについて加算していけばよい。mの最大値はN+K程度であることに注意。
割とすんなり解けた。
C: 共通部分列が無いってことは反転すれば良さそうだなとか言って、中心を求めてぐるんぐるんしてみたけど通らない。コンテスト後、木の直径が奇数⇔中心が2つある場合を考慮して同じことをしてみたらなんか通った。証明は出来ていない。
木の中心とかいうのを久しぶりに求めたので忘れていたが、中心は2個ありうるというのはちゃんと頭に置いておくべきだった。
D: 何も分からない。
Categories: 未分類