AtCoder Beginner Contest 137
地獄だ…
A +-x
やるだけ。
Aとはいえサンプルの確認しちゃいますよね。
B One Clue
これもやるだけですね。サンプルが合うようにコード書けばOKです
C Green Bin
問題：N個の文字列でアナグラムになっている組を求めよ
考察：
それぞれの文字数があっていればよいのでmapで記録すればよいです
D Summer Vacation
問題：N個の仕事がある。i個目の仕事はAi日後にBi報酬が得られる。1日に1件まで請けてM日後までの報酬を最大化せよ
考察：
直感的に大きい順に取るか早い順に取るかに絞られます
なんか寿司の問題かなんかで後ろから取ることが良かったのでやってみたら最適だと示せます。
後ろからみてM-j日目に行ってM日目までに得られる仕事は、Ai<=jのものです
その中で報酬が最大のものを行い、うけれる仕事のリストから消します
この操作を円滑に行えるデータ構造として、C++ならmultiset、pythonならheapqが挙げられます。便利なデータ構造です。ほんとに
E Coins Respawn
問題：N頂点M辺の有向グラフが与えられる。各辺を通るとCiのコインが得られる。2回目以降も得られる。頂点Nでゲームを終了し獲得コインー通った辺の数*Pが最終スコアになる。スコアを最大化せよ
考察：
ScoreAttackです。そういう問題があります。
ScoreAttackが嘘解法で通っていて1時間半バグり続けました～完～
解説：
ベルマンフォード法というアルゴリズムがあります。負の辺に対応した最短距離を求めるアルゴリズムでO(VE)で動きます
ベルマンフォード法は各頂点N回未満しか距離が更新されないことに着目し、N回目で距離が更新された場合負閉路に含まれているとわかるアルゴリズムです。
今回辺の重みを-1*(Ci-P)とすると頂点1からNの最短距離問題に帰着できます
負閉路がある場合、無限に距離を小さくできる(スコアを伸ばせる)ため、その頂点の距離を-infにします
この-infが全ての頂点に影響するまで最大N回かかるので、もう一度ベルマンフォード法を使えばよいです。
感想：
ScoreAttackのケースが弱かったのが悪い(嘘だよー)
F Polynomial Construction
問題：素数pについて全てmod pで考える
p個の方程式
ai=f(i)=bp-1*x^(p-1)+...+b0
が与えられる
p次ベクトルbを求めよ
考察：
明らかに変数p個も式p個の連立方程式です
行列にして掃き出しましょう。
O(p＾3)でTLEが出せます。
以下のブログを参考にさせて頂きました。
まずかったら該当箇所は消します。
解説：
ラグランジェ補間というものを使うらしいです
使いどころがイマイチわかってないんですが、多項式を解くときとかなんですかね
ラグランジェ補間：
p個の点(x,y)を通るy=f(x)を求めることができる
fi(x)=(x-x0)(x-x1)…(x-x(i-1))(x-x(i+1))…(x-x(p-1))
こうしたとき、x=xiのときfi(xi)、そうでないとき0になる関数が出来上がります。
fi(x)をyi/fi(xi)倍すればx=xiでyiになる関数が出来上がります。
これをp個足すことでp個の点を通ることができました。
元の問題に戻ります。(xi,yi)=(i,ai)です。
最後に求めるべきbiは、x^jの係数です。
fi(x)を展開して係数を足していけばよいです。しかし愚直にやるとO(p^3)かかってしまします。1回の積でp、p個の積、p個の関数なので。
x-xiもかけたものは全関数で共通そうなので、前計算で計算量を減らせます。
したがってO(p^2)で解けました。
感想：
そもそもらしいを知らなかったです。しかも、知ってても思いつくか怪しいですね。
実装も軽くなくて、多項式の計算とか書いたことなかったのでかなり苦労しました。
このレベルがコンテスト中に通せればだいぶレート伸びそうです。自分はまだまだ
