heno239’s blog

まとめたいことをまとめる

技術室奥プログラミングコンテスト#5 Day1 感想

  • コンテストリンク

https://yukicoder.me/contests/284

  • 問題ごとの感想

  1. 【A問題】A問題のwriterであるkaageさんをそのまま提出しました。★1(というかエイプリルフール的問題？)
  2. 【B問題】連続するa_i!=b_iをまとめてひっくり返すのを繰り返します。★1.5
  3. 【C問題】L=1のとき2^N-1になるのは知識の問題。L>1でもNを(N+L-1)/LにすればL=1に帰着できる(?未証明)。結構困惑したので★2
  4. 【D問題】3桁以上の時、各桁は0か3か6か9でないといけない。2桁以下の場合は3の倍数かどうかを全探索、3桁以上の場合は{0,3,6,9}の4通りを10桁分全探索(計算量4^10)。★1.5で投票したけど沼に落ちるとつらそう(?)
  5. 【E問題】はじめなぜかM<=10^9に見えて時間をロスしてしまった。列を左からみるとN*1(たて)を1個おくか、1*N(よこ)をN個おくかになるので、後者の数を全探索すると、あとはコンビネーションで解ける。★2
  6. 【F問題】「Dの倍数」という条件がなければシンプルな二分探索、あったとしてもN未満の数字xについてはx か x-1のどちらかはDの倍数ではないので、判定をxとx+1両方で行うと二分探索できる。★2
  7. 【G問題】LIS祭りって感じ。一昔前なら★3とかになるかもしれないけど、かなり典型になってしまったので★2かなあ。
  8. 【H問題】かなり戸惑った。同じ数字を2度以上使うことはないので、長さNの数列を長さ1024に数列(i番目には数字iが何回与えられる数列に存在するかを持つ)に圧縮し、dp[i][j]:=(今までのxorがi,今までとった個数がj個)のdpを遷移させた。B=MAX{A}とおくと、計算量はO(B^2logB)。★2.5
  9. 【I問題】辺を行って戻ってを繰り返せば2の倍数は楽に稼げるので、各頂点では{スタート/ゴール}から{偶/奇}数回でくるときの最短路を求めればよく、頂点倍化してdfsで求めた。★2.5
  10. 【J問題】A=0が無いのが救い。昇順で条件を満たすものの個数を数え上げてN!倍すればよい。最小値をiに固定すると、(S_{i+1}-S_i)の合計をD=min(M,i+B)-N*(A-1)以下に抑える問題になり、この値は(D+N-1,N-1)。★3
  11. 【K問題】これかなり良い問題だと思う。-1となるケースは文字列Sが文字列Tの部分列となるケース。そうでないとき、貪欲に小さいものをとり、それを取った後にちゃんと条件を満たす文字列が作れるかを判定したくなる。判定の具体例として、S=ba??,T=a???のときに1文字目にaをとったとする。このときSの後ろの??がTの後ろの???の部分列になっているようでは、条件を満たすような文字列が作れなくなる。これを一般化すると、結局判定パートではSのあるsuffixがTのあるsuffixの部分列になるかどうかが必要になる。これはSを後から見ていって、「TのsuffixでSの現在のsuffixを部分列に持つ」ものの中の最小値を更新していくと、判定できるようになる。★3.5
  12. 【L問題】期待値の線形性を使って丁寧に数え上げる。★3
  13. 【M問題】辺に登場しないところはA_i=iのまま。そうでないところは、いくつかの辺を伝っていくことができる頂点のうち最大値にする。これは愚直にやるとO(M^2)だが、SCCを使うとO(M)でできる。★3
  14. 【N問題】通称挿入DP。DP[i][j]:=i番目のアルファベットまで見てj個アルファベットがある場合の数とすると、DP[i+1][j+k]+=DP[i][j]*(j+k)!/(j!*k!)という遷移になり、畳み込みの形になる。2894msでかなりTLが危なかった。★3.5
  15. 【O問題】構文解析やるだけ。演算の順序等がややこしくバグりやすいので★3.5
  16. 【P問題】オンラインで重心分解をしよう！★4

 

  • 全体的な感想

ノーペナかつ爆速という最高のパフォーマンスでうれしい。

day2も楽しみ。