No.519 アイドルユニット - yukicoder n (2の倍数, 24以下) 人のアイドルでn/2組のペアを作る。それぞれのペアの相性がn*n行列で与えられるとき、ペアの相性の和の最大値を求めよ。 nが小さいのでペア成立済みのアイドルを状態にしたbitDPでメモリとしては十…

agc015.contest.atcoder.jp N * M のグリッドに0または1が書いてあり、1をノード、1が隣同士になっているときにはエッジが張ってあるとみなすと、1の集合はTreeになる。領域(x[1,i],y[1,i], x[2, i], y[2,i])がQ個与えられるので、その領域でTreeの部分集合…

agc015.contest.atcoder.jp 各階に上または下のボタンしかないエレベーターがある。最上階は下、1階は上であるときに、i階からj階に移動する全組み合わせについて移動の最低回数の合計値を求めよ。 移動の最低回数は多くても2回。なので、すべての組み合わせ…

最近はDeep Learningのモデルを書くときは大体Kerasを使っています。理由は Outputの次元を定義するだけで書ける Layer型のDNNライブラリでめんどくさそうなRNNやLSTMなどは標準で入ってる 学習が簡単(ミニバッチの生成などを余り考えなくてもかける) Backen…

joi2017yo.contest.atcoder.jp H*Wの高度マップが与えられる。水をあるマスに流すと、低い高度で隣接するマスに流れ、自マスからは水が消滅する。そのようなマスが2個以上隣接してる場合は、そのようなマス全てに水が流れる。周りがすべて自マスより高い高度…

joi2017yo.contest.atcoder.jp M種のぬいぐるみをN個並べる。N個の中から一斉に幾つか取り出し、順番を変えて元に戻した時同一種類のぬいぐるみは全部隣り合う用に並べたい(11112222223333 のように) 取り出す数の最小値を求めよ。 Mが20程度なのでBitDPを疑…

arc074.contest.atcoder.jp 2次元マップ上の複数の場所oとスタートとゴールが与えられる。が与えられる。x軸またはy軸が等しい場所o及びスタート、ゴールはワープすることができる。このとき、スタートからゴールにたどり着けなくするためにoを取り除きたい(…

arc074.contest.atcoder.jp (l[i], r[i], x[i])の組がM個与えられる。Nマスを赤 緑 青で塗り分ける時、[l[i], r[i]]の範囲はx[i]色になるという制限を課す。塗り分け方は何通りか。 何通りか、なのでdpで考える。 n番目まで色を塗って、一番最後に塗った色と…

arc074.contest.atcoder.jp 長さ3Nの数列a[i]が与えられる。この中から2N個を選び「前半N個の総和 - 後半N個の総和」を最大化せよ。 前半N要素が全て入っている範囲を[0, k), 後半N要素が全て入っている範囲を[k, N)として、N<=k

gigazine.net 「自動コンパイル」という謎の造語が出てきて、コメント等をみてもいまいち記事が正確に伝わってない気がします(Gigazineの翻訳の問題かもしれませんが…)。英語の原文だと「Compilable」とかになっていましたが、これはオンラインのコーディン…

agc009.contest.atcoder.jp 袋X, Yがあり、S[i]の数字が書かれたN個のボールが与えられる。それぞれの袋の中ではボールの数字の差がそれぞれA以上、B以上になっているように振り分けたい。そのような振り分け方は何通りあるか？ A < Bとなるように必要があれ…

agc002.contest.atcoder.jp N色(色1～色N)のボールがそれぞれK個づつある。これらを並び替え、各色の先頭にあるボールを全て同じ色(色0)に塗る。並び方は何通りあるか？ こういう問題ではボールをノードとして捉え、ノード間の順番制約をエッジとして表現で…

shiropen.com 論文はここ。 http://cs.stanford.edu/~michels/publications/michels_2017_stiffly-accurate-integration/michels_2017_stiffly-accurate-integration.pdf 質点同士の相互作用の物理モデルとして減衰振動モデルというのがあります。 減衰振動 …

abc061.contest.atcoder.jp 負経路を許す有向グラフで、頂点1から頂点Nまでの最長経路を求めよ。いくらでも長くできる場合はinfを出力せよ。 辺のコストを-1倍してベルマンフォード。負閉路が検出されたその時点でinfにする。ただし、1からNへの経路に関係な…

codeforces.com 2者がそれぞれn文字の集合を持っていて、さらに????で埋まったn文字のマスがある。両者が互いに?を自分の文字を使って埋めていく。先行は辞書順最小、後攻は辞書順最大になるように最適な戦略を取る時最終的にできる文字列を答えよ。 先行を…

整数列s, tが与えられる。sの整数列について、次の操作LまたはRを施す。 操作L：{..., a[i], a[i+1], a[i+2], ...} -> {..., a[i] + a[i-1], a[i+1] + a[i], a[i+2]+a[i+1], ...} 操作R：{..., a[i], a[i+1], a[i+2], ...} -> {..., a[i] + a[i+1], a[i+1] +…

対応が正規の括弧列の文字列与えられる。この文字列に対し以下の操作を行う。 左端の開括弧を削除 除去後も括弧列が正規であるような任意の閉括弧を1個削除する この操作を繰り返し行なった後、空文字になるパターンは何通りあるか。 括弧列の問題は後ろから…

最近のガチャは確率pで当たりが出ます、というだけじゃなく天井と言うものが設定されてることがあります。これは、例えばガチャにある一定の数nが設定され、その中で必ず1枚は当たりがある、といったものです。とりあえずこれをモデル化してみます。 流石に…

agc014.contest.atcoder.jp N頂点からなる木について、交互に白黒白と色を塗っていくゲームをする。最後に1回だけ、黒が隣接している白の点を一斉に黒にする。この時白が残っていれば白の勝ちである。最適に行動したときにどちらが勝つか求めよ。 木の葉が2…

codeforces.com ツリーTが与えられて、Tの各頂点v[i]にアイスクリームの集合s[i]が与えられる。同一のアイスが含まれる頂点だけからなる部分グラフは連結である。この時、新しいアイスの集合を頂点とするグラフGを、Tのある頂点v[i]があって、アイスaとアイ…

arc073.contest.atcoder.jp (x[i], y[i]) (1≦i≦N) が与えられる。任意の点について、xとyを交換できるとき、これらの点をすべて含み、辺がx軸またはy軸に平行な長方形の面積の最小値を求めよ。 まずすべての点についてx[i]≦y[i]となるようにしておく。この時…

Dashboard - Round 1C 2017 - Google Code Jam 円柱型のパンケーキをN枚の中からK枚選択して、大きい順に重ねたとき底面を除いた表面積を最大化せよという問題。 まず側面を除いた面積は最大の半径を持つパンケーキの上面の面積に等しい。なので、パンケーキ…

RのProxy設定はぐぐると色々出ては来るのですが、それでもトラブルが多いのでメモ。 まず同じProxyでも以下のパターンが存在します。 Proxyのホストとポートを指定し、Proxy自体に認証はなし Proxyのホストとポートを指定し、Proxy自体に認証がある pacスク…