AHCで疲れていたので、unratedで参加してAだけ解いて終了。
B - Pass on Path
自力AC。
どの休憩所からスタートし最初に進む方向を右・右、右・左、左・左と決めると、二分探索を使えばどこでぶつかるかが分かるので、それぞれ計算していく。というコンテスト中に思いついた方針で解けた。
結構実装が大変。コンテスト中は、方針は思いつけても実装する気力がなかった。
……と思ったが、「二人は同じ休憩所からスタートする」ものだと思って解いていた。別な休憩所からスタートしてもOKだとACしてからツイッターを見て気付いた。
同じ休憩所からスタートして良いというの、あんまり明らかに思えないので、正しく読解していたら解けなかったかも……。
C - Pivot
自力ACしたが、大量にペナを出してしまった。
「通常の状態」と「反転した状態」を分けて考え、それぞれの変化はgcdになりそう……といったあたりは結構すぐ思いついたので、それをきちんと詰めれば答えにたどりついたのだが。きちんと詰めるのがなかなか大変だった。
D - Halftree
自力ACしたが、時間がかかってしまったのでコンテスト中解けた気がしないなぁ。
Nが偶数のときは作れない。
Nが奇数で、NとKのgcdが1のときは、Kおきに順番に繋いでいけばOK。
それ以外のとき。右へいくと+1、下へいくと+Kすると考えると、縦をgcd、横をN/gcdとしたグリッドとみなすことができる。
このグリッドが縦横ともに奇数なことを利用して、木を作っていく。
3*3での木の作り方を考えて、それをコピーしていく……と考えた。3*3のマスで木を作る（「N」の文字におまけがついたようなやつにした）。
これをそのままコピーするとサイクルができてしまうので、一番上の行の以外では一ヶ所辺を減らせばOK。
E - Xor Annihilation
解説放送を見てAC。
問題文の読解が困難だったけど、maspyさんのツイートで理解しました。
・ボールの重み全部のxorは0である
・累積xorを考える
・ボールが合体することは、累積xorの一項が消えることに対応する
というところまで気付けると、解説のような立式ができる。
一つ目、二つ目は考えたが、三つ目に気付けなかった。
ただ実験するだけでなく、「累積xorを使うと何か上手い性質が見つかるのでは？」と予想して実験するのが大切か。
0 件のコメント:
コメントを投稿