参加してきました
コンテスト以外のことも書きます
Day0
たまたま午後の授業がなかった(夏休みは1カ月前に終わっている...)ので、15:00くらいの飛行機で東京へ
編入前の友人と会ってハンバーグを食べて英気を養う
データサイエンティストになりそうと言ってたので、AtCoderをやってほしいな～と思いながら...
前も誘って緑くらいで忙しくてやめちゃってたので復帰してほしいけど、大学院がすごく大変そうだった
その後は友達の家に泊めてもらってゆっくりねた
Day1
気合入れようと思って友達とお昼から焼肉を食べた、おいしかった
泊まっていたのは大塚だったので山手線で田町まで
ちゃんと場所が見つかるか不安だったけど、近くの建物にkaedeさんがいて案内してくれた
会場で受付をして、スポンサーのサントリーさんから飲み物をもらって着席
半分ちょいくらい人がいたのでちょうどいい時間だな～と思いながらゆっくりした
席にはクリアファイルとかシールとかがあって置いてあった
みんなそれなりに早く来ていてakenshoさんがびっくりしていた
ちゃんと来ているのに遅刻オッズ1位のnoimiさんかわいそう
スケジュールに開会式って書いてあったからどんなものかなと思っていたけど、ふつうにchokudaiさんがしゃべってゆる～く終わった
特にやることもないのでライブラリとかをみながら時間を待ってコンテスト開始
A Apple Addiction
300点ね～、OKと思っていたけど開いてみると、典型だけど明らかに300ではなさそうな問題が置いてあります
気持ちを落ち着けながら考察を進めていると、周りが爆速でタイピングし始めてびっくりします
考察はそんなに重くなくて、どうせdp[i] := i番目を食べたときのmaxなので、遷移を詰めていきます
長さKはかぶってもよくK以上に言い換えられるので、そのまま伸ばす or 新しく長さKの区間をとるのどちらかをすればよく、
dp[i] = max(dp[i-1] + A[i], max(dp[0] ~ dp[i-K]) + sum[i-K+1 : i] )
という遷移になります
なんかうまいことできそうだな～と思うんですが、セグ木で自明にできるのでmaxのセグ木を使って遷移を書きます
多少バグらせるけど直すとサンプルも普通に合うので提出してAC
(AC 22:03)
B Max Degree Sum
600はさすがに解かないとまずそう + 解けそうなので次はBに行きます
最初とっかかりがなくてどうしようと思いますが、いろいろいじっていると
・両方の端点がk以下
・片方の端点がk以下
・両方の端点がkより大きい
の優先順位で結ぶのがよさそうだと思います
両方の端点がk以下となる辺はどんどん増えていって消えることはないので、これをとりあえずつなげていくUnion Findを準備します(木にしないといけないので閉路を防ぐ)
これで「両方の端点がk以下となる辺」の数はわかるので、この辺数 × 2が答えに加算されます
ほかに答えに関係するのは「片方の端点がk以下となる辺」です
これは「k以下の頂点から伸びている辺」なので、k以下の頂点から1手で到達できる頂点を列挙しておきます
ここにある頂点にはとりあえず伸ばすのが最善なので、到達できる頂点数分増えるのかな～と思って実装します
これは実装するとサンプルが合いません
もう少し考えると、同じ頂点に複数本伸ばしても閉路にならないことがあるなと思います
今までは「到達可能な頂点」を考えていましたが、逆に「到達不可能な頂点」を考えると、その頂点と連結にするために1頂点につき1本辺が必要なので、「到達不可能な頂点」の数を引けばいいかな？と思います
実装するとサンプルが合うので提出するとWA
後半パートがちょっと怪しそうなのでもう少し考えます
上の実装は、到達できない頂点以外は「片方の端点がk以下」の辺を使うことを前提としています
ただ、手元でグラフを作っているとその前提を満たせないケースがあります
そのような場合は「両方の端点がkより大きい」辺で結ぶことになります
このような辺の数は、k以下の頂点から伸びている辺をすべて使った別のUnion Findを用意しておき、その連結成分数をみる(=1でなければkより大きい頂点同士で連結にするしかない)ことでわかります
これをまとめて
(両方の端点がk以下で使う辺) × 2 + (木にするためにまだ必要な辺) - (1手で到達できない頂点の数) - (2つめのUnion Findの連結成分数 - 1)
で求めることができます これでAC
(AC 46:20)
E Min Subtraction
Cを解こうか悩んだんですが、もうかなり解かれていて賞金を狙うには900必須(ワンチャンABD, ABEでいけない？)と思ったので、どっちかというと解けそうだと感じたEをやります
まず1回の操作で少なくとも1つは0になります
おきもちとしては、左から右に進めていくように連続して0をつくっていけると結構得する + 最終的に両方0がつくれるとアツいと思います
操作を始める場所を決め打つと、偶奇を分けたときに開始位置からの和の大小関係が単調増加 or 単調減少になっているといいことがわかります
このあたりをうまく使おうと思っていたんですが、始点が変わると大小関係も簡単に変化してしまってどうしようもなくなってしまいました
クリティカルっぽい考察も生まれなかったので賞金はあきらめてCを解くことにしました(1時間~1時間30分くらい消費)
C Power Convergence
700だし苦手よりな数学問だしな～と思って避けていたんですが、Eが虚無すぎたのでCを解くことにします
とりあえず移項すると x^k (x-1) ≡ 0 (mod N)になるので、うまくできそうな気がします
すぐに気づかなかったんですが、よくよく考えるとxとx-1は互いに素になるので、mod Nで0(Nで割り切れる)になるためにはNの素因数をxとx-1に割り振る必要があります
そうすると以下のような条件を満たす数を見つけることになります
・xとx-1は互いに素である (常に満たされる)
・x-1はNの素因数のうちいくつかを持つが、Nの素因数の指数以上でなければならない
(12 = 2^2 × 3なら、 2^1はダメで2^2でないといけない)
・xはx-1に含まれないNの素因数を持たなければいけない
(こちらはk乗するので、指数が足りていなくてもOK)
ざっくり考えると、x-1側を決め打つとxに含まれないといけない素因数がわかるので、x-1を決め打とうと思います
これは、x-1がAで割りきれる = xをAで割るとあまり1、xはBで割り切れるという2つの条件になるので、CRTを使うと該当する数を求めることができます
具体的なものも書いておきます
N = 12とすると、 N = 2^2 × 3なので考えられるパターンは以下の通りです
・x-1が1で割り切れる xが6で割り切れる -> f(x) = 2
・x-1が1で割り切れる xが12で割り切れる -> f(x) = 1
・x-1が3で割り切れる xが2で割り切れる -> f(x) = 2
・x-1が3で割り切れる xが4で割り切れる -> f(x) = 1
・x-1が4で割り切れる xが3で割り切れる -> f(x) = 1
・x-1が12で割り切れる xが1で割り切れる -> f(x) = 1
※x-1が2で割り切れるというのは、素因数2があまってしまうのでダメ
これらそれぞれについて、CRTで該当する数を求め和を取ればいいのですが、実はかぶりがあります
・x-1が3で割り切れる xが2で割り切れる -> f(x) = 2
・x-1が3で割り切れる xが4で割り切れる -> f(x) = 1
このようなものを数えようとすると、xが2で割り切れる数にはxが4で割り切れる数も含んでいるので、いい感じに処理しなければいけません
＝＝＝コンテスト中ここまで＝＝＝
これは典型的な問題で、大きい方から除原理のように解いたり、約数の高速メビウス変換をしたりなどで、重複を取り除けます
除原理をすると、x-1を決め打つパートがあるので、見た目的には約数の個数をDとしてO(D^3) になるかもしれませんが、適切に枝を刈るとO(D^2)になる(と思います)
(AC --:--)
コンテスト後
Cを解ききれず、う～んと思いながら企業プレゼンを聞いた
普通に内容はおもしろかったけど、ヒューリスティックの方が大事そうだなと思った
そもそも今のところ入学枠の都合で一般企業への就職がダメなので、そういう人で申し訳ないなと思いながら聞いた
表彰式は観客としてワクワクしながら見てた
tatyamさんでも10位なのか～と思っていたら、vwxyzさんが6位ですごーとなった
vwxyzさんの名前が呼びにくそうだった
3~5位はいつもの強い人たちだな～という感じで、1,2位は順位表的にpotatoさんとSSRSさんの争いぽかったのでどっちなんだろと思っていたら、SSRSさんが優勝していた
初観測したのでこんな人なんだと思ったけど、感想とかしゃべってもらって人柄をざっくり把握したかったな～
懇親
ご飯を食べながら懇親会で何人かお話しした
Twitterで見たことある人じゃないとしゃべりづらい...
karinohito, sotanishy, nok0, zkou, nawa, AngrySadEight (敬称略) + UNICORNやALGO ARTISの社員さんと話した
ALGO ARTISの人になんであんなに優秀な人ばっかりなんですか？って聞いたら、全力の引き抜き + 盛んな社内勉強会でレベルアップというのを聞いて、すごくいい環境だな～って思った
懇親会後はnok0さん、zkouさん、karinohitoさんと4人でガストに行った
ハイライト
・緑~水色のころコードを見ていると、同じBFS記事をコピペしていて無意味すぎるコメントが一致
・zkouさんがnok0さんに「これ解けないのやばいよ～」と詰められているのを観測
・ABC見ながら「Dやばいよね」ってみんなでわちゃわちゃする
みんなFPS分野が強くてぼくも逃げてられないなと思った
22:00すぎくらいまで色々話して解散
浜松町にホテルを取ってたので向かって就寝
春にはオンサイト(UTPCとか？)ありそうで学校も休みなので、競プロしに行こうかなと思ってます
交流してくださった方、開催してくださったAtCoder社そのほかありがとうございました！！！
