ARC074 D - 3N Numbers
長さ3Nの数列a[i]が与えられる。この中から2N個を選び「前半N個の総和 - 後半N個の総和」を最大化せよ。
前半N要素が全て入っている範囲を[0, k), 後半N要素が全て入っている範囲を[k, N)として、N<=k<N*2 の範囲で最大値を求めればよい。ナイーブにやるには毎回ソートして前半であれば最大値からN番目までの和を求めれば良いが、これでは計算量がO(N^2)なので間に合わない。
そこで、PriorityQueueを使ってある時点kでの総和の最大値から、k+1での総和の最大値をO(logN)で計算する。具体的にはa[k]をQueueに追加し、最小値minを取り出す。するとdp[k + 1] = dp[k] - min + a[k] となる。これを前半後半両方で2個dpすると、その差の最大値が答え。O(N logN)。
「インドのプログラマーでちゃんと自動コンパイルできるコードを書いているのは36％」の意味
「自動コンパイル」という謎の造語が出てきて、コメント等をみてもいまいち記事が正確に伝わってない気がします(Gigazineの翻訳の問題かもしれませんが…)。英語の原文だと「Compilable」とかになっていましたが、これはオンラインのコーディングチェックとか競技プログラミングをやったことある人じゃないとかなり伝わりにくい内容に見えました。
これはざっといえばAtCoderやPaizaなどのオンラインのコーディングチェックのような問題を2問出して、Submitできてかつコンパイルエラーにならなかった人が36％しかいなかった、という意味になります。以下で詳しく説明します。
まず、オンラインのコーディングチェックというのは通常次のような形式で問題が提出されます。
入力A(1<=A<=1,000,000,000,000)に対して、A+1を標準出力に出力するようなプログラムのソースコードを提出せよ。実行時間は2秒以内とする。入力はすべて標準入力からなされる。
注意すべきところは 提出すべきものはA+1はなく、実行バイナリでもなく、ソースコードであるという点です。これを提出すると次のような作業が始まります。
この時、1番でコンパイルエラーにならなかった人が全体の36％というのがこの記事の言いたいことです(少なくともそう読み取れました)。
さて、ここまで書くとそもそもコンパイルできないソースしか書けない人なんているのか？という話はあるのですが、実はこれ思っているよりも結構難しいです。
例えばソースコード提出時に言語を選ぶのですが、この言語を間違って選択してしまった場合や、提出するコードにゴミが混じってしまっていた、認められてない(サーバ側にインストールされていない)ライブラリを使ってしまっていた、gccのバージョンが違っていた、Javaであればパッケージを分けてしまっていた、などの可能性が考えられます。
また、問題が難しくてそもそもどういうコードを書けばいいかわからなかったというのもあるでしょう。(上の例ではそんなことありませんが、難易度の高い問題だと結構あります)
原文のレポートはこちらにあるのですが、さらに3.が終わってすべてのテストケースに通った人は全体の2.21％だったそうです。
また、このシステムの目的として更にテストケースに通った人の中でメンテ可能なコードを書ける人、効率的なコードを書ける人の割合を示しており、いずれの要素も満たすプログラマは2.21％の中の更に6割ぐらいしかいなかった、と書いてありました。
AGC009 C - Division into Two
袋X, Yがあり、S[i]の数字が書かれたN個のボールが与えられる。それぞれの袋の中ではボールの数字の差がそれぞれA以上、B以上になっているように振り分けたい。そのような振り分け方は何通りあるか？
A < Bとなるように必要があればswapしておく。
dp1[i]をi番目のボールをXに格納する組み合わせ、dp2[i]をi番目のボールをYに格納する組み合わせとする。
まずYの方について、自由にボールを入れるとする。つまりdp2の更新だが、単純に既に既に入っているボールの最大値を見る。
dp[i + 1] = Σdp2[k] (kはS[k] + B <= S[i + 1]の範囲) となるが、これは尺取＋累積和を使うことでO(1)で計算可能。
次にdp1はdp2という制約の元(既に幾つかのボールがYに入っているという制約)、S[i+1]-S[i]がA未満かそうでないかで漸化式が異なる。A未満ならば一つ前は必ずYに格納されており、その次にXに格納される。ただし、S[i+2] - S[i] < Aというボールがあった場合は事前に0を出力しておく。そうでない場合はdp1[i + 1] = dp2[i] となる。
A以上の場合、一つ前のぼーるがXだろうとYだろうとどっちでも良いのでdp1[i + 1] = dp1[i] + dp2[i]である。
全体でO(N)。
いろんな漸化式が組めるが高速化すると上のように落ち着くらしい。
AGC002 F - F - Leftmost Ball
N色(色1～色N)のボールがそれぞれK個づつある。これらを並び替え、各色の先頭にあるボールを全て同じ色(色0)に塗る。並び方は何通りあるか？
こういう問題ではボールをノードとして捉え、ノード間の順番制約をエッジとして表現できたらトポロジカルソートの個数となる。トポロジカルソートの個数は一般に求める方法があるわけではないが、単純なグラフならdpで数える。これが基本方針。
各色だけ取り出すと「色0 色i 色i 色i...」という並びになる。その他、一番右にあるボールがすべて塗られるので、右から見ていった場合、色0のボールの数が、それまで登場した色の数よりも必ず大きくなる。なので、一旦色の順番を固定すると、結局以下のようなグラフになる。
(図はEditorialより拝借)
このトポロジカルソートとして可能な個数をカウントし、色の順番としてありうる数N!を乗じると答えになる。トポロジカルソートとして可能な個数のカウントは一般的なアルゴリズムがあるわけではないが、頑張ってdpでカウントする。O(N^2)。
人間の髪のような変形可能な複雑な物体を今までより現実的にシミュレートする論文を読む
論文はここ。
質点同士の相互作用の物理モデルとして減衰振動モデルというのがあります。
簡単に言うと質点の座標を p=(x, y, z) とおくとpの2階常微分方程式になるものです。Wikipediaの数式だと外力なしですが、右辺にf(p)等を置くことで外力を考えた減衰振動モデルになります。
この減衰振動モデルを高次元化、つまりp=(x1, x2, x3, ....) とし、それぞれの係数を行列に置き換えることで剛体の減衰振動モデルが構成できます。この剛体の減衰振動モデルは人間の髪の毛等の変形モデルなど複雑な物体のシミュレーションモデルとして使えることがよく知られています。
この論文ではそのようなモデルに対して、より正確にpの数値計算を行うアルゴリズムを提示しています。既存の手法だと、例えばニュートン法を用いて微分値を初期値にどんどん足していく、と言った単純な手法がありますが、この方法では大域的に見ると徐々に解析解とのずれが積み重なり現実の動きと遠いモデルになってしまいます。
そこでこの論文ではまず元のモデルの数式をちょっと改良し(論文中ではReforming Elastdynamic Systemsとかいてあります)、時間積分を指数関数的に行う(同様にExponential Integration)方法を構築し、そのモデルをクリロフ射影アルゴリズムと言う既知のアルゴリズムに最適化することで計算量を抑えるという構成にしています。
かなり意訳すると、今までの手法では一次近似の繰り返しであったため、局所的にはシミュレートできても大域的には現実と程遠い挙動になってしまったところを、指数関数的な時間発展を考えることで高次の項もかんがられた時間発展ができるようになった、という感じでしょうか。
論文の最後の方に簡単な擬似コードも乗っており、親切な論文です。
AtCoder Beginner Contest 061 D - Score Attack
負経路を許す有向グラフで、頂点1から頂点Nまでの最長経路を求めよ。いくらでも長くできる場合はinfを出力せよ。
辺のコストを-1倍してベルマンフォード。負閉路が検出されたその時点でinfにする。ただし、1からNへの経路に関係ない負閉路が存在する場合があるのでそこは考えない。簡単な方法としてdfsでNに行くことが可能な頂点がtrueであるようなbooleanの配列を作っておき、負閉路チェックの際にfalseであればスルーするなどがある。
いわれてみればそうなんだけど、負閉路検出の条件に気づかずにハマった。しかももっと単純に書けるかもしれない。
Codeforces Round #414 C - Naming Company
2者がそれぞれn文字の集合を持っていて、さらに????で埋まったn文字のマスがある。両者が互いに?を自分の文字を使って埋めていく。先行は辞書順最小、後攻は辞書順最大になるように最適な戦略を取る時最終的にできる文字列を答えよ。
先行を昇順ソート、後攻を降順ソートすると、それぞれ(n+1)/2, n/2文字目までしか使わない。これらをとりあえずキューに入れる。先頭の文字が先行<後攻を満たす間は貪欲にマスの先頭を自分の文字列の先頭の文字で埋めていく。
その後ある時点で、先頭の文字が 先行＞=後攻 となる。この時点から、自分の持っている一番悪い文字(先行なら辞書順最大、後攻なら辞書順最小)を一番影響の少ないところ、つまり一番うしろから詰めていく。O(N)。
これできないのはちょっと頂けなかった。多分典型問。
