アルゴリズム忘備録

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

「インドのプログラマーでちゃんと自動コンパイルできるコードを書いているのは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のパッケージをイ…

AtCoder Regular Contest 072 E - Alice in linear land

arc072.contest.atcoder.jp はじめ距離0にいて目的地が距離Dのところにある。計画{d1, d2, ..., dN}があって、i回目の行動でd[i]進んだとき、現在地点よりも目的地に近くなるならばその方向に進む。通り過ぎた場合は折り返しもあり。この計画のqj番目を書き…

Yukicoder Contest 161

No.505 カードの数式2 - yukicoder よくある数字を加減乗除した時の最大値を求める問題…であるが本番解けず。Nが小さいので思わず全探索してしまったがTLEする。変な貪欲をやってみたがもちろん合わず。 正しい方法はi項目まで使った時の最小値及び最大値を…

AtCoder Regular Contest 062 - E - AtCoDeerくんと立方体づくり

arc062.contest.atcoder.jp 正方形がN個(N≦400)与えられ、それぞれの正方形の四隅には異なる色C[i,j] (C[i, j]≦999)がついている。この正方形を6個使って立方体を作るとき、隅の色を合わせる組み合わせは何通りあるか。ただし、回転したものは同一のものとみ…

New Year Contest 2015 C - 文字列の書き換え

nyc2015.contest.atcoder.jp 文字列が2個与えられる。任意の場所に直前の文字と違う任意の文字を挿入という操作を繰り返すとき、与えられた最初の文字列を2番めの文字列に変換できるか? 文字を追加していくと考えると、最後の文字にだけ依存する条件なので…

IRT + Stan でらくらくスコアリング

テスト問題を作成する時に困るのが配点です。できれば問題の難易度に応じて配点を決めたいのですが、問題の難易度の推定は意外と難しいです。そこでTOEICなんかではIRTという方法が使われています。 数理モデルはWikipeida当たりに詳しいのでそちらを参考に…

SRM712さぼった

TODOリスト代わりのメモ。Easyのみあとでやる。

AtCoder Grand Contest 013 C - Ants on a Circle

agc013.contest.atcoder.jp 本番解けず。ありがぶつかるとき、方向を反転させるのではなく互いにすれ違い方向はそのまま直進と考えるのが定石の問題(参照:蟻本) ただこの問題の場合、今仮想的に直進している「1番」の蟻(実際は反転を繰り返しているので1番…

Mo's Algorithm

前これを使う問題をCodeforcesでみた(解けなかった)のでメモ。 a[1] ... a[N] (N=O(10^6)) に対し区間クエリQ(l, r)がO(10^6)個発行される。このクエリは先読み可能である。Q(l, r)の結果がわかっているときに隣接クエリQ(l±1, r), Q(l, r±1) の結果はO(1)と…

2017 TCO Marathon Round 1 が始まります

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=55119&rd=16903 競技プログラミングには短時間で100%正解を求めるアルゴリズムマッチ(正式名称しらない)と、長時間でなるべく高い得点を稼ぐマラソンという分野があります…

AtCoder Grand Contest 012 D - Colorful Balls

agc012.contest.atcoder.jp ボールが一列に並んでいる。異色の場合、重さの合計がY以下なら任意の2個を入れ替えることができる。同色の場合、重さの合計がX以下なら任意の2個を入れ替えることができる。色の並び順として何通りあるか? 自力で解けなかった。…

サルでもわかる因果関係推論

データ分析をしていると、分析要件として因果関係の分析をすることになるケースが結構あったりします。そこでやりがちなのが、相関関係を因果関係と誤解してしまうケースです。例えば以下のようなケース。 例えばデータXが勉強時間、データYが成績のとき、X…

Yukicoder 483 マッチ並べ

No.483 マッチ並べ - yukicoder 無向グラフの辺を有向化する。その時→←のような辺があるかどうか判定せよ。 以前解いたときはN=100かつ条件を満たす探索の枝刈りがとても効率いいので、単なる自然なdfsの全探索で通してしまった。 ループが2個以上あるときは…

Google Code Jam 2017 Qualification Round

Dashboard - Qualification Round 2017 - Google Code Jam 無事通過。でも全部解きたかったなあ。 A: 1次元ライツアウト。 右から貪欲にそろえていけばよい。O(length S) B: 左から数字が増加していくようなもの(1111222255566とか)をTidiy Numberと呼ぶ。N…

AtCoder Regular Contest 071 E TrBBnsformBBtion

arc071.contest.atcoder.jp A~BB, B~AA, AAA~(空文字), BBB~(空文字) と編集可能とする。 文字列SとTが与えられたときに、クエリS[a, b] T[c, d]が同値かどうか答えよ。 ただし、文字列が同値とは編集を繰り返して別の文字列にたどり着くことと定義する…

AtCoder Regular Contest 071 D 井井井 / ###

arc071.contest.atcoder.jp x軸に平行な直線がm本、y軸に平行な直線n本、あり、それぞれのy座標、x座標はy[i], x[j] である。これらの交点を使って任意の長方形を作る。そういう長方形の面積の総和を求めよ。 x軸とy軸で独立して考える。x[i]からx[i - 1]の…

AtCoder Regular Contest 071 F Infinite Sequence

arc071.contest.atcoder.jp {1,…,n} からなる無限長の列 a1,a2,… のうち、 次の条件を満たしているものは何通りあるでしょうか? 第 n 項から先はすべて同じ数である。つまり、n≤i,j ならば ai=aj を満たす。 どの正の整数 i に対しても、第 i 項の直後に並…

Google Code Jam 2017 Qualification Round(予選) が明日の朝8時から開催されます

code.google.com 予選ある程度プログラムが書ける人なら結構簡単で、しかも一日以上開催されてるのでぜひ参加してみましょう。具体的なスケジュールは以下ですが、デフォルトだとUTCで表示されてるので、右上のLocal Timeをクリックして現地時間で見てみると…

Yukicoder 502 階乗を計算するだけ

No.502 階乗を計算するだけ - yukicoder n (0≦n≦10^18) のとき、n! (mod 10^9 + 7) を計算せよという問題。 普通にやるとn!の計算はO(n)かかる。nがmodの値(=10^9+7)以上のときは恒等的に0であるが、それでもO(10^9)で間に合わない。ちょっとしたテクニック…

Mujin Programming Challenge 2017 A Robot Racing

mujin-pc-2017.contest.atcoder.jp N(1≦N≦100000)体のロボットがそれぞれ座標x[i]≧0にいる。これらの任意のロボットを左に1または2移動させる(飛び越えられる)とき、ゴール(座標が負)する順番は何通りあるか? 言葉で説明するのが難しいアルゴリズム。右から…

みんなのプロコン 本戦B チーム決め

yahoo-procon2017-final-open.contest.atcoder.jp ある命題が成立する最小値xについて、任意のx’≧xについて同様に成立するときの最小値を求めよという問題であれば、からなず二分探索をするべき。 これもまずチーム間の実力差の最小値kを仮定して矛盾がある…

データ解析のための統計モデリング入門 レビュー

データ解析のための統計モデリング入門――一般化線形モデル・階層ベイズモデル・MCMC (確率と情報の科学) 作者: 久保拓弥 出版社/メーカー: 岩波書店 発売日: 2012/05/19 メディア: 単行本 購入: 16人 クリック: 163回 この商品を含むブログ (29件) を見る い…

TopCoder Open Round1A

Easy(250) 卓球台があって、最初試合待ちの人が順番に並んでる。それぞれint[] skillの値のスキルを持っている。 対戦はskillが高いほうがかならず勝つ。先頭に並んでる人が対戦し、負けた人は最後尾に、ただしN連勝したら勝った方も最後尾にいく。K回後の対…

AtCoder Grand Contest 012 B - Splatter Painting

グラフを考える。ある頂点から距離d(0≦d≦10)以内を色cで塗る、というクエリをQ(0≦Q≦10^5)個処理するとき、最終的な各頂点の色を求めよ 一番最後のクエリのみが反映される→クエリを逆順に考える dが小さいのでナイーブにやってもC++ならできそう。ただしJava…

アルゴリズム忘備録

このブログでは主に下記2点について記事を書きます。 競技プログラミングで使用したアルゴリズムの忘備録 データ分析の一般論 ガジェット・技術書のレビュー 1.については考え方のみを書く予定。コードは載せる予定はないです。 2.については最近やってるこ…