競プロ日記

あけましておめでとうございます。
新年初記事。
年末に記事を書きたかったけど時間がなかったのでまずは2日連続のコンテスト参加記事から。

問題

順位: 1193

パフォーマンス: 1256

新レーティング: 1075

差分: -27

1完。
初めてAGCに参加したが、さすがに難しかった。
目覚めたらコンテスト開始してて、なんとか頑張って9:10過ぎから活動開始した。
結果論だが、Aは一瞬で解けて終わりなので最初から参加していればもっとパフォーマンス出てそう。
寝起きによる自身のパフォーマンスも含めて。

直近のABC148 Fとすごい似てるなーという第一印象。
偶奇があっていれば2人とも全て勝ち続ければ出会う。
偶奇を合わせるためにはどちらかが同じ場所に留まる必要があり、端でしか留まることができないので、端に近い人が端に行って1回留まれば良さそう。
普通にAC。
考察から実装まで5分ちょっと。
寝坊のせいで20分になってしまった。

この問題を2時間近く考えて結局解けなかった。
解析的に解け・・・ない。
二分探索でき・・・ない。(！)
二分探索に使うような関数で全問題に対して可能かどうか走査・・・いけそう？
というような流れで、計算量抑えつつなんとか実装できないか色々してたら解けなかった。
二分探索の発想に至るのにおそらく1時間以上かかったのはまだしも、そこからダメの判断を下したのは非常にbad。
単調増加であるという判断ができなかった。
PやVの値によって場合分けしていたのだが、場合分けしていることが問題を必要以上に複雑にしてしまった。

よく考えてみると、ある問題Xが可能であるとすると、問題Xよりスコアが大きい問題Yと問題Xの選び方を入れ替えると、Yを選ぶことが可能となる。
ただそれだけなのに、何点入れればある問題を選ぶことが可能で、残りの点数はどのように振り分ければ他の問題がある点数以内に収まるか、ある点数以内に収まるようにすると点数が余る場合はどのようにすれば良いか。
こんなことを考えていた。
ある問題を選ぶことが可能であるかどうか知りたいだけなので、M人全員が1点ずつ選ぶとして良い。
それに気付けなかったのが敗因。

ややこC。
問題文とドミノの配置を理解するのに相当時間がかかった。
偶数(偶数は色々便利そうと考えた)で一番小さい4×4について手作業で考えてみようと思ったが、それすらちょっと考えただけでは分からなかったので、その先は無理だろうということでBに専念。
ただ実際には、苦労してでも4×4を実装することが本筋だった。
マス目が小さい値でクオリティが同じものを構成すれば、後はそれらを組み合わせて対角線上に配置すれば、全ての行列でクオリティを保ったままになる・・・なるほど。
2の場合は不可能、3の場合はクオリティ1を作成でき、4, 5, 6, 7の場合はクオリティ1は作成できないが、クオリティ3のものを作成でき、4, 5, 6, 7があれば8以上は全て作成できるのでこれで考える必要のある構成は全て。

相当パズル要素強い。
競プロの大部分を占めるであろう数学系とかシミュレーション系しか解いたことがないので、こういった問題は面白いと感じるが、さすがに引き出しがなさすぎるからその方向に考えを移行できない。
もっと余裕持って問題解きたいね

見てまーーーーーせん。
ABCなら解けなくてもコンテスト終了後に解説見て云々あるのだが、解説すら見ていない。
ちょっとレベルが違いそうで解くのはいつになるやら。

まとめ

初めてのAGCだが、一応レートは上がったので変な苦手意識を持たずに済んだ。
B問題はdiff水色だし解けても良かったなー。

また原因を寝坊に求めることもできるが、そもそも最近まともに頭働いていない状態からコンテストに参加することが多くて反省している。
起きてから本稼働開始までに3,4時間かかる人間なので、本来ならもっと早く起きておくべきなのだが、年末だしねということでひとつ。

年内目標だったブログの移行はまだ少しかかりそう。
水色もブログの移行も年内無理だったかぁ。