データ分析をしていると、分析要件として因果関係の分析をすることになるケースが結構あったりします。そこでやりがちなのが、相関関係を因果関係と誤解してしまうケースです。例えば以下のようなケース。 例えばデータXが勉強時間、データYが成績のとき、X…
No.483 マッチ並べ - yukicoder 無向グラフの辺を有向化する。その時→←のような辺があるかどうか判定せよ。 以前解いたときはN=100かつ条件を満たす探索の枝刈りがとても効率いいので、単なる自然なdfsの全探索で通してしまった。 ループが2個以上あるときは…
Dashboard - Qualification Round 2017 - Google Code Jam 無事通過。でも全部解きたかったなあ。 A: 1次元ライツアウト。 右から貪欲にそろえていけばよい。O(length S) B: 左から数字が増加していくようなもの(1111222255566とか)をTidiy Numberと呼ぶ。N…
arc071.contest.atcoder.jp A～BB, B～AA, AAA～(空文字), BBB～(空文字) と編集可能とする。 文字列SとTが与えられたときに、クエリS[a, b] T[c, d]が同値かどうか答えよ。 ただし、文字列が同値とは編集を繰り返して別の文字列にたどり着くことと定義する…
arc071.contest.atcoder.jp x軸に平行な直線がm本、y軸に平行な直線n本、あり、それぞれのy座標、x座標はy[i], x[j] である。これらの交点を使って任意の長方形を作る。そういう長方形の面積の総和を求めよ。 x軸とy軸で独立して考える。x[i]からx[i - 1]の…
arc071.contest.atcoder.jp {1,…,n} からなる無限長の列 a1,a2,… のうち、 次の条件を満たしているものは何通りあるでしょうか？ 第 n 項から先はすべて同じ数である。つまり、n≤i,j ならば ai=aj を満たす。 どの正の整数 i に対しても、第 i 項の直後に並…
code.google.com 予選ある程度プログラムが書ける人なら結構簡単で、しかも一日以上開催されてるのでぜひ参加してみましょう。具体的なスケジュールは以下ですが、デフォルトだとUTCで表示されてるので、右上のLocal Timeをクリックして現地時間で見てみると…
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-pc-2017.contest.atcoder.jp N(1≦N≦100000)体のロボットがそれぞれ座標x[i]≧0にいる。これらの任意のロボットを左に1または2移動させる(飛び越えられる)とき、ゴール(座標が負)する順番は何通りあるか？ 言葉で説明するのが難しいアルゴリズム。右から…
yahoo-procon2017-final-open.contest.atcoder.jp ある命題が成立する最小値xについて、任意のx’≧xについて同様に成立するときの最小値を求めよという問題であれば、からなず二分探索をするべき。 これもまずチーム間の実力差の最小値kを仮定して矛盾がある…
データ解析のための統計モデリング入門――一般化線形モデル・階層ベイズモデル・MCMC (確率と情報の科学) 作者: 久保拓弥 出版社/メーカー: 岩波書店 発売日: 2012/05/19 メディア: 単行本 購入: 16人 クリック: 163回 この商品を含むブログ (29件) を見る い…
Easy(250) 卓球台があって、最初試合待ちの人が順番に並んでる。それぞれint[] skillの値のスキルを持っている。 対戦はskillが高いほうがかならず勝つ。先頭に並んでる人が対戦し、負けた人は最後尾に、ただしN連勝したら勝った方も最後尾にいく。K回後の対…
グラフを考える。ある頂点から距離d(0≦d≦10)以内を色cで塗る、というクエリをQ(0≦Q≦10^5)個処理するとき、最終的な各頂点の色を求めよ 一番最後のクエリのみが反映される→クエリを逆順に考える dが小さいのでナイーブにやってもC++ならできそう。ただしJava…
このブログでは主に下記2点について記事を書きます。 競技プログラミングで使用したアルゴリズムの忘備録 データ分析の一般論 ガジェット・技術書のレビュー 1.については考え方のみを書く予定。コードは載せる予定はないです。 2.については最近やってるこ…
