2022年1月7日金曜日

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)

　Fまで六完。

コンテスト後のツイート

G - Balls in Boxes

　解説放送を見てAC。

　この問題（ブログ内の記事）の類題だったが、身に着いていなかった。配り方に帰着するというのは覚えていたのだけど、実際にどうやるのかが難しい。

　他にも、これやこれが類題だった。

　積の和を求めるのはなかなか難しくて、配り方へ帰着するしかない（ことが多い）、ということは頭に入っているのだけど、実際に解こうとすると頭がこんがらがってしまう。
　今納得できているけど、次回出たとき解けるかはあまり自信ないなぁ……。

H - Minimum Coloring

　解説放送を見てAC。

　フローを使いそう、とはコンテスト中も分かったが、その後のグラフの構築は大変。「容量下限付き最小費用流」のグラフの構築の仕方は勉強になった。とはいえ、しっくりきたかというとそこまでいっていないのが難しい……。一応納得したつもりではあるのだが。
　snukeさんのブログ記事にも大体同じ内容があるので、分からなくなったときはここも参考にしたい。

　なお、自分が元々持っていた最小費用流ライブラリだとTLEしてしまったので、少しだけ高速化した（それでもギリギリだった）。
　他の方のライブラリと同じことをしているつもりなのだけど、まだ若干遅いのは何故だろう。
時刻:
ラベル: , ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)