na_o_ysのブログ

プログラミングのメモ

コンテナ時代の Twelve-Factor App

Twelve-Factor App (Adam Wiggins, 2012) を読んで感動したので、あらためてコンテナ技術が流行する 2016 年現在の Web アプリケーション環境を意識しながら覚え書き、まとめです。 本記事は主に Web アプリケーション開発者、Web アプリケーションインフラ…

Haskell で始める AtCoder Beginner Contest

Competitive Programming Advent Calendar 2015 五日目の記事です。 www.adventar.org Beginner Contest レベルなら、呪文みたいな大量のコード (レギュラーコンテストに出てる人たちのコードはすごい) を書かないでも、意外とシンプルに書けることが多くて…

ICFPC 2015 参加記

ICFPC2015 にソロで出た。刺激的な三日間でした。 一日目 朝 問題を読む。 ハニカム構造のテトリスの AI を作れば良いらしい。 Ruby でコマンドラインで可視化しながら Qualification Problems の json を読む。 12:00 Problem 1 を単純に左下詰めで提出して…

どうぶつしょうぎの盤面認識アプリを作る (4) 駒の認識

(1) 準備編 (2) 勉強編 (3) 盤面の正規化 (4) 駒の認識 正規化された入力画像から、各駒の位置を取得します。 駒 (先手ゾウ) の位置を特定 概略 駒の画像を用意する テンプレートマッチングで駒の位置を特定する 駒が傾いている場合を考慮して、複数の角度で…

どうぶつしょうぎの盤面認識アプリを作る (3) 盤面の正規化

(1) 準備編 (2) 勉強編 (3) 盤面の正規化 (4) 駒の認識 カメラで撮影した画像から、盤面のみを取り出して固定位置に正規化します。 入力画像 正規化後の入力画像 手法 盤面のみの画像を用意する 入力画像と盤面画像で特徴量抽出・マッチングする マッチング…

どうぶつしょうぎの盤面認識アプリを作る (2) 勉強編

(1) 準備編 (2) 勉強編 (3) 盤面の正規化 (4) 駒の認識 画像を盤面情報(駒の配置、持ち駒)に変換するためには、次のような処理が必要となる。 画像内でのボードの座標取得 画像内での各駒の座標取得 上記内容をもとに盤面情報を計算・生成 1, 2 はあらかじ…

どうぶつしょうぎの盤面認識アプリを作る (1) 準備編

(1) 準備編 (2) 勉強編 (3) 盤面の正規化 (4) 駒の認識 会社の人たちと一泊二日の開発合宿@伊東温泉をすることになりました。 この機会に初めての画像認識にチャレンジしてみようと思います。 2日間で作りきる自信が全く無いので、この記事は前日夜にこそ…

join から理解する State モナド

すごいH本 14 章に出てきた State モナドの理解が難しかったので, まとめてみました. State モナドとは 状態付き計算を表現するモナド 現状態 s1 を受け取り, 値 a と次状態 s2 のペアを返す関数 newtype State s a = State { runState :: s -> (a, s) } s: …

(unrated) SRM 644 Div1 Easy, OkonomiyakiParty

SRM

問題 N (< 50) 種類のお好み焼きがある. i 番目の大きさは配列 osize[i] (< 10000) で与えられる. このうち M (< N) 種類を選ぶときに, 最も小さいものと最も大きいものの差が K 以下となるような選び方は何通りあるか, 1,000,000,007 の剰余で求めよ. 方針 …

Codeforces Good Bye 2014 C, New Year Book Reading

問題 http://codeforces.com/contest/500/problem/C 本が N (< 500) 冊ある. それぞれの本には重さがある. 本は全て重ねて積んだ状態である. 上から I 番目の本を読む場合には, I 番目の本を取り出して山の一番上に移動させる. この時, あなたには 1~I-1 番…

Codeforces Good Bye 2014 D, New Year Santa Network

方針を考えるのが楽しい問題だった. 問題 http://codeforces.com/contest/500/problem/D ノード数 N (< 100000) の木が与えられる. 各辺は長さを持つ. 1 年に一回, ある辺の長さが更新される. 3 頂点 a, b, c を一様ランダムに選んだ時の, D = distance(a, b…

SRM 640 Div1 Easy, ChristmasTreeDecoration

特に引っ掛けは無いので, 方針だけ思いつけば簡単な問題. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13551&rd=16083 N (<50) 個の星と M (<200) 個のリボンがある. 星はそれぞれ色があり, i 番目の星の色は col[i] で与えられる. リ…

SRM 643 Div1 Med, TheKingsArmyDiv1

SRM

コーナーケースに気をつけて慎重に戦略を考える問題(もしくはDP解法). 本番では題意を微妙に取り違えていて, なぜか pretest 通ってしまい, 呆気無く撃墜された. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13526&rd=16086 2N 人の…

SRM 643 Div1 Easy, TheKingsFactorization

SRM

本番は素数リスト作ったけどその必要も無かった. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13594&rd=16086 1018 以下の整数 N が与えられる. N を素因数分解せよ. ただしヒントとして, 昇順 0, 2, 4, 6, ... 番目の素因数が与えられ…

SRM 641 Div1 Easy, TrianglesContainOrigin

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13309&rd=16084 2 次元平面上の点が N (< 2500) 個与えられる. これらの点が構成する三角形のうち, 内側に原点を含むものの個数を求めよ. 方針 偏角でソートし, 全ての点 i, j (i < j) につ…

SRM 642 Div1 Med, TaroCutting

Med は難しい... 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13319&rd=16085 木が N 本ある. n 番目の木は高さ height[n] であり, 1 日に add[n] だけ伸びる. また, カッターが M 個ある. m 番目のカッターをある木に対して使うと, 木…

SRM 642 Div1 Easy, WatingForBus

DP の練習に良い問題だとおもった 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13540&rd=16085 同じ停留所に発着するバスが N (< 100) 台あり, 0 から N-1 までの番号が割り当てられている. i 番目のバスが発車してから戻ってくるまで…

社会人 2 年目が競技プログラミングを始めた 1 年を振り返る

この記事は Competitive Programming Advent Calendar Div2014 12 日目です。 競技プログラミングを始めて 1 年がたちました。この一年をざっと振り返ってみたいと思います。 【1 月】PrintScreen / Aizu Online Judge 新卒 SIer 1 年目だった僕は、一日 8 …

SRM 639 Div1 Easy, AliceGame

SRM

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13490&rd=16082 Alice, Kirito 2人がゲームをする. ゲームはターン1から始まり有限ターンからなる. 各ターンでそれぞれ勝者が決まり, i ターン目で勝利すると2*i-1ポイントもらえる. long l…

Haskellでエラトステネスのふるい (Data.Set編)

最近、Project Euler の問題をぽちぽち解いていってます。どうせやるなら慣れていない言語でやろう!ということで Python とか Haskell を触ってるのですが、イミュータブルなデータ構造が基本の Haskell でアレコレやるのは本当に難しい。 例えば Problem 1…

SRM 638 Div1 Med, NarrowPassage2

本番では解けなかったけど, 綺麗な DP 問題だった. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13295 廊下に N (<= 50) 匹の狼が配置されている. 各狼のサイズは vector<int> size で与えられている. 二匹の狼がすれ違えるのは, サイズの合</int>…

SRM 638 Div1 Easy, ShadowSculpture

SRM

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13355&rd=16081 N*N*N (N <= 10) の空間に 1*1*1 のキューブをいくつか配置する. XY・YZ・ZX平面の投影図がそれぞれ与えられる. 配置したキューブは全て隣接し得るかどうか答えよ. 方針 座…

SRM 633 Div1 Easy, PeriodicJumping

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13234&rd=16076 int x, vector<int> jumpLengths が与えられる. 二次元平面上の原点 (0, 0) からスタートして, 点 (x, 0) に到達したい. 平面上を jumpLengths で与えられた距離だけ順に移動する</int>…

SRM 632 Div1 Easy, PotentialArithmeticSequence

SRM

問題 a[0], ..., a[N-1] の N 個の非負整数がある. ただし, a は与えられない. 代わりに, 2進数表現での trailing zero の数 d[0], ..., d[N-1] が与えられる. a[0], ..., a[N-1] について, 1 ずつ増加する部分列の個数の最大値を求めよ. 1 <= N <= 50 0 <= …

SRM 630 Div1 Med, SuffixArrayDiv1

SRM

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13377&rd=16061 ある文字列に対する接尾辞配列 SA が与えられている. 元の文字列は何種類のアルファベットで構成されているか. 最も少ない場合の種類数を求めよ. 接尾辞配列 - Wikipedia 文…

SRM 630 Div1 Easy, Egalitarianism3

SRM

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13284&rd=16061 頂点数 n, 辺数 n-1 の木が与えられる. 各辺には距離が設定されている. k 個の頂点を選び, 頂点間の距離が全て等しくなるようにしたい. k の最大値を求めよ. 頂点数は 1 以…

SRM 628 Div1 Easy, DivisorsPower

SRM

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13241&rd=16009 は x の 1 以上 x 以下の約数の個数を表す. とする. 与えられた整数 について, を満たす最小の x を求めよ. 存在しない場合は -1 を返す. 解法 より, の値は最大でも60であ…

SRM 627 Div1 Easy, HappyLetterDiv1

SRM

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13274 [a-z] のみからなる文字列 L (1 <= |L| <= 50) が与えられる. 一度の操作で, 文字列中の任意の異なる文字ペアを消去する (例えば "aabbc" -> "aab"). この操作を繰り返して, 最後に残…

SRM 627 Div1 Med, GraphInversions

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13275 N 頂点, N 辺 (3 <= N <= 1000) の連結な無向グラフが与えられる. 各頂点は属性として値 v_i (1 <= v_i <= 1000) を持つ. 長さ K 以上の全ての単純路について, それぞれ v_i の系列で…

Binary Indexed Tree (BIT, Fenwick Tree)

概要 整数列 に対して, 以下のクエリを O(log(n)) で実現するデータ構造. : を求める : に を加える 特徴 Segment Tree の機能縮小版で, 実装がむちゃくちゃ簡単. 構造 深さ log(n) の二分木であり, 各ノードは以下の法則で値を保持する. 葉: 葉の親: 葉の親…