アルゴリズム忘備録

競技プログラミングとかデータ分析とか

D: Game on Tree - AtCoder Grand Contest 017

agc017.contest.atcoder.jp 木の根を含まない部分木を交互に取り除いていき、操作ができなくなった(根しかない状態になった)ほうが負けとする。最適な行動を取る時先手後手どちらが勝つか? Green Hackenbushとかいう有名問題とのこと。明らかにGrundy数であ…

C: Snuke and Spells - AtCoder Grand Contest 017

agc017.contest.atcoder.jp 数列A[i]が与えられる。この数列は時刻tにX[i]番目がY[i]に変化する。時刻tでの数列に於いて、「k個の数がある時、kの数字を削除する」という操作を繰り返すことで数列を空にしたい。そのためには時刻tでの数列から何個の数字を変…

C: Splitting Pile - AtCoder Regular Contest 078

arc078.contest.atcoder.jp 数列a[i]が与えられる。|(a[1]+...+a[k]) - (a[k+1]+...+a[N])|を最小化せよ。 a[i]の累積和sum[i]を計算しておくと、(a[1]+...+a[k]) 及び (a[k+1]+...+a[N]) はそれぞれO(1)で計算可能。これでkを全探索すればよい。O(N)。

B: Moderate Differences - AtCoder Grand Contest 017

agc017.contest.atcoder.jp 長さNの数列を構成したい。最初と最後の要素がA, Bで与えられる。また、隣り合う要素同士の差はC以上D以下になるようにしたい。このような構成は可能か? 最初の要素を除くN-1個の要素について、k個が前の要素以上、N-1-k個が前の…

A: Biscuits - AtCoder Grand Contest 017

agc017.contest.atcoder.jp 数列A[i]が与えられるので、部分列をとってその和の余りを0または1にしたい。そのような部分列は何通りあるか? k番目までの数列の部分列をとったときにあまりが0または1になる組み合わせをa[0][k], a[1][k]とおく。A[k + 1]が奇…

C: 節約生活 - AtCoder Regular Contest 007

arc007.contest.atcoder.jp 最大10の周期でxoxooxoxxという並びが繰り返す。この周期と同じ周期を幾つか用いて、それぞれ任意の数だけずらして重ねたときに少なくとも1個の○が存在するようにしたい。最小でこの周期を何個使えばいいか。 周期の長さを持つ01b…

C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008

arc008.contest.atcoder.jp N人の人が(x[i], y[i])にいる。それぞれ最大t[i]の速度でたこ焼きを投げられ、また最大r[i]までの速度で投げられたたこ焼きをキャッチできる。一人目の人が1秒おきにたこ焼きを投げ、その他の人もたこ焼きを受け取ったらそれを更…

E: guruguru - AtCoder Regular Contest 077

arc077.contest.atcoder.jp 整数xを一つ決める。ある数a[i]に対して、a[i] + 1 またはxに遷移する、という操作を行い、a[1]~a[n]までの遷移を実現する。この操作の回数が最小になるようにxを決めた時、その最小回数を求めよ。 素直にやるとO(NM)の問題で当…

D: 11 - AtCoder Regular Contest 077

arc077.contest.atcoder.jp 1~nの数で構成された、n+1個の数列が与えられる。この数列の中で、1~nはそれぞれ少なくとも1回以上は登場する。この時、長さ1~n+1の部分列で、異なる個数の総和を求めよ。 要はある数が一つだけダブっており、それ以外は全部1…

C: pushpush - AtCoder Regular Contest 077

arc077.contest.atcoder.jp 数列a[i]が与えられる。このa[i]とある空の別の数列b[j]について、bの末尾にa[i]を加え、bをreverseする、という操作をすべてのa[i]について繰り返す。最後にできる数列を求めよ。 毎回Reverseするのではなく、Nが偶数なら最後に…

E: Connected? - AtCoder Regular Contest 076

arc076.contest.atcoder.jp RxC の平面内に (x1[i], y1[i]) (x2[i], y2[i]) の座標のペアが幾つか与えられる。このペア同士で線を引きたいが、それぞれの線が交差してはならない。そのような引き方が可能かどうか判定せよ。 まず、両方の点のいずれかが周囲…

D: Built? - AtCoder Regular Contest 076

arc076.contest.atcoder.jp 座標(x[i], y[i])に街がある、街間に道路を引くためにはx座標の差またはy座標の差の小さいほうの距離だけコストがかかる。いくつか道路を引いて全部の街を行き来できるようにするための最小コストはいくつか? 最小全域木を求めれ…

C: Reconciled? - AtCoder Regular Contest 076

arc076.contest.atcoder.jp 犬がN匹、サルがM匹いる。犬同士、サル同士が互いに隣り合わない並びかたは何通りか? |N - M| > 1 の場合は0通り。 |N - M| == 1 のときは、xoxoxoxox という並び順しかありえないのでN! * M! 通り。 |N - M| == 0 のときは、oxo…

AtCoder Grand Contest 016 C: +/- Rectangle

agc016.contest.atcoder.jp H行W列の整数値のテーブルで、h行w列の部分区画の和はすべて負、かつテーブル全部の要素の和が正であるようなテーブルは存在するか?するなら具体例を示せ。 具体的な構成を色々試すと、右下の角1マスだけ負、それ以外は正である…

AtCoder Grand Contest 016 B: Colorful Hats

agc016.contest.atcoder.jp N匹の猫が色付き防止をかぶっている。それぞれの猫は自分以外の猫の帽子の色がa[i]種類あるといっている。このような組み合わせは存在するか? ある猫に注目したときにその猫をカウントする・しないで最大1種類しか違わない。よっ…

AtCoder Grand Contest 016 A: Shrinking

agc016.contest.atcoder.jp アルファベット小文字からなる文字列がs[i]で与えられる。新しい文字列のi番目の文字をs[i] or s[i + 1] のいずれかを選んで構成する、という作業を行う。この作業を何回か繰り返して全ての文字が単一のアルファベットで構成され…

交渉をするAI

code.facebook.com Facebook Research Blogに面白いAIの記事が出ていました。自然言語(英語)で交渉をするAIを作ってみたという記事です。シチュエーションとしては、2者がそれぞれ何個かのアイテムを所持しており(公開情報)、それぞれのアイテムに2者それぞ…

AtCoder Regular Contest 075 E - Meaningful Mean

arc075.contest.atcoder.jp 数列が与えられる。連続部分列の平均値がK以上であるような部分列は何通りあるか? まずすぐ分かることはすべての要素からKを引くと、部分列の和が0以上になるような組み合わせをカウントすればよい。これはO(N^2)であれば、累積…

画像認識 (機械学習プロフェッショナルシリーズ) レビュー

画像認識 (機械学習プロフェッショナルシリーズ) 作者: 原田達也 出版社/メーカー: 講談社 発売日: 2017/05/25 メディア: 単行本(ソフトカバー) この商品を含むブログを見る 比較的新しい画像認識の本。ただ構成が独特で、画像認識の一般論といった基礎を…

AtCoder Regular Contest 075 D - Widespread

arc075.contest.atcoder.jp 魔物の体力s[1]~s[N]が与えられる。一回の魔法攻撃で、特定の一つの魔物の体力をA削り、その他すべての魔物の体力をB削る。ただしA>Bとする。全滅させるには魔法攻撃を最低何回打てばよいか? C=A-Bとする。魔法攻撃の回数をkと…

Educational Codeforces Round 22 C. The Tag Game

codeforces.com 木の2個の頂点にAさん及びBさんがいる。AさんがBさんを追いかけ、BさんはAさんから逃げるという目的で行動を最適化するとき、AさんがBさんに追いつく手数を求めよ。その場にとどまるのもありとし、Bさんが先手とする。 Aさん及びBさんがいる…

Yukicoder 524 コイン

No.524 コイン - yukicoder N(0

Codeforces 417 B. Sagheer, the Hausmeister

codeforces.com n階m部屋と両脇に階段(よって全体の幅はm + 2)の建物がある。最初は1階の左はじにいる人が各階の電気をすべて消し、上にのぼる、次の階もすべて消し上にのぼる…を繰り返してすべての部屋の電気を消す。最初に点いている部屋が与えられる時、…

Yukicoder No.520 プロジェクトオイラーへの招待

No.520 プロジェクトオイラーへの招待 - yukicoder 三角形の各辺について、a個、b個、c個の内分点が与えられる。頂点及び内分点同士で直線を互いに交わらないように引けるだけ引く。線の引き方は何通りあるか? 真ん中に三角形ができるパターンと出来ないパ…

Yukicoder No.519 アイドルユニット

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

AGC015 C - Nuske vs Phantom Thnook

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 B - Evilator

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

Kerasによる深層強化学習(DQN)

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

第16回日本情報オリンピック 予選 E - 尾根 (Ridge)

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

第16回日本情報オリンピック 予選 D - ぬいぐるみの整理 (Plush Toys)

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

ARC074 F - Lotus Leaves

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

ARC074 E - RGB Sequence

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

ARC074 D - 3N Numbers

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

「インドのプログラマーでちゃんと自動コンパイルできるコードを書いているのは36%」の意味

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

AGC009 C - Division into Two

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

AGC002 F - F - Leftmost Ball

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 質点同士の相互作用の物理モデルとして減衰振動モデルというのがあります。 減衰振動 …

AtCoder Beginner Contest 061 D - Score Attack

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

Codeforces Round #414 C - Naming Company

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

SRM712 Div1 Easy LR

整数列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] +…

SRM714 Div1 Easy Parenthesis Removal

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

Rでガチャ推定

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

AtCoder Grand Contest 014 D - Black and White Tree

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

Codeforces 411 Div.1C Ice cream coloring

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

AtCoder Regular Contest 073 E: Ball Coloring

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

Google Code Jam 2017 Round 1-C A

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

RのProxy設定

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

TopCoder Open Marathon Match Round1

TopCoder グラフのノード及びエッジ、そのエッジの「長さ」が与えられる。このグラフのノードを700x700の整数座標に配置するときに、エッジの「長さ」になるべく近くなるような配置を求めよ。 私はエッジをバネと見立てた力学系のモデルを組んでみました。そ…

square869120Contest #4 C - Calendar 2

s8pc-4.contest.atcoder.jp 昔解いた問題の忘備録。 a[i]が与えられる。幅7マスでn行あるカレンダーについて、すべてのa[i]について、mで割った余りがa[i]であるようなマスを黒く塗る時の連結成分の個数を求める問題。 まず最初に7nがmの倍数であるようにa[i…

RでYahoo Japanの株価データにアクセスする

昔はPerlでパーサを書いて取得したりしたんですが、最近はRに便利なパッケージがあってほぼコマンド一つで株価データにアクセスできるようです。 > install.packages("quantmod", dependencies = TRUE) > library("quantmod") まずquantmodのパッケージをイ…