naoya_t@hatenablog

いわゆるチラシノウラであります

天下一プログラマーコンテスト

4/20(土) 21:00-22:40
feat.海鮮焼きそば
1完0ペナ269位、パフォ1993でレートを少し持ち直した (1627→1670, +43) 。
f:id:n4_t:20190420234854p:plain
上位陣もD以降で苦戦していたようで実質Cの早解きだった。

C - Stones (300)

  • 白が左側に、黒が右側にそれぞれ0個以上固まっている状態に持っていけばよい
  • どこが切れ目になるか、をN+1通り全て試せばよさそう
  • 累積和を持っておけばそれぞれO(1)で、合計でO(N)

AC 6:08

D - Three Colors (600)

  • 最長辺の長さは[\frac{1}{3}〜\frac{1}{2})の範囲になる
  • 最長辺として許される範囲に何本で到達できるかDPする?
    • O(N^4)になるのでは(無理)
  • 全組み合わせ数から許されない組み合わせ数を引く?
    • 最長辺が1/2以下になるものを排除?
    • いずれにしてもO(N^4)なのでは

飛ばして次へ

E - Polynomial Divisors (800)

  • a_iの最大公約数(の素因数)が含まれるのは自明
  • x^2-x+2 = x(x-1)+2で、x(x-1)が必ず偶数(2の倍数)になることから全体は2で割り切れる
  • p=a_Nの約数(あるいは0)ついて、多項式の定数項以外が x-p で割り切れるか見る。
    • 例えば (x-1)(x-2)(x-3) のように3つ連続で割り切れるなら必ず3の倍数、とか?

詰めきれずに次へ

後で

自分の方針ではサンプルは通るけどWA

けんちょん先生の記事を読んだ


  • 任意の整数xに対して多項式f(x)pで割り切れる
  • f(x)x(x-1)(x-2)...(x-(p-1)) で割った余りが0 (\mod\ p)

ここでx(x-1)(x-2)...(x-(p-1))=x^p-xが言えるので

  • f(x)x^p-x で割った余りが0 (\mod\ p)
    • g(x)=x^p-x と置くとき、任意の x=[0,p) に対しフェルマーの小定理からg(x)≡0が成り立つ。
    • ということは g(x)≡x(x-1)\cdots(x-(p-1))h(x) で、次数がどちらもpで、p次の係数が1、ということはh(x)=1、よって x^p-x≡x(x-1)\cdots(x-(p-1)) (\mod\ p) が言える
    • なるほど…
  • pN以下(の素数)だけ試せばいい
  • x^p≡x (\mod\ p) なので、余りは次数をp-1で割った余りに寄せた p-1 次の多項式で表せる
  • この係数がすべてpで割り切れる、即ち f(x)≡0 (\mod\ p) なら、元の多項式pで割り切れる

AC
ワーイ

F - Banned X (800)

  • [012]のみから成る長さnの数列で、合計がXになるのは何通りか?という問いの答えは用意できる
    • これを利用して、区間合計がXになる全パターンを列挙できるか?
  • こね回してみたものの、重複排除がうまくできない