HackerRank Week of Code 33 参加日記

262位/11880人。Easy問は省略する。 Transform to Palindrome n種類の文字で構成された、長さmの文字列sがある。ここで、Transform[x,y]は、文字xをyへ、または文字yをxへ変換できることを意味する。k個のTransformが与えられたとき、sを変換してなるべく長…

Codechef May Challenge 2017 参加日記

CodechefのLong Challengeに初参加した。221位/7492人Chef and his daily routine Chefの一日は必ず、料理・食事・睡眠の順番である。1日の行動ログが料理'C'、食事'E'、睡眠'S'の形式で与えられたとき、これが有効かどうかを答えよ。 1 C・E・Sの順番にな…

HackerRank Week of Code 32 参加日記

396位/8447人の不本意な結果。レートも少し落ちた。 以下、Easy問題は省略する。 Circular Walk 次の式が与えられる。 円周上にn個の点(0~n-1)があったとき、点iから距離R[i]までジャンプすることができる。たとえばR[i]が2であれば、{i-1, i-1, i, i+1, i+2…

HackerRank Week of Code 30 参加日記

289位/10554人でレートほぼ変化なし。以下、難易度EasyとMediumのものは省略する。Poles 斜面上にn本のポールがあり、それぞれ高度x[i]と重さw[i]が与えられる(高度はユニーク)。これをk本のスタックにまとめたい。 ・スタック位置はもともとポールがあっ…

Maximum closure problem

Maximum closure problem の学習まとめ。以下のサイトを参考にした。Closure problem - Wikipedia http%3A%2F%2Friot.ieor.berkeley.edu%2F~dorit%2Fpub%2Fscribe%2Flec11%2FLec11posted.pdf&usg=AFQjCNEhubnfNuotTV0_wrbkGGdEF9UHMA&sig2=ewamZFzAoKgnMP5Fa…

CodinGame - Ghost in the Cell 参加日記

CodinGameのコンテストに初参加してみた。ゲームAIを作ってその強さを競うものなのだが、面倒な環境構築が不要でなかなか楽しかった。対戦動画も観ていて面白い。https://www.codingame.com/replay/194505045 黄色が私。最終的にCyborgの数が多いほうが勝ち…

HackerRank Ad Infinitum16 参加日記

始めて参加した。数学関連の問題がでるコンテストらしい。 46位/673人だけど初回参加者用の区分だっただからレベルが低いのかも。ad Infinitum: 無限に、永久に(ラテン語) Leonardo's Prime Factors q個の整数が与えられる。それぞれの整数(nとする)につ…

イントロソートを安定ソートとして習作(C#)

C#

C#で安定ソートを行うときはLinqのOrderBy()が一般的だが、OrderByはクイックソートなのでワースト計算量がO(N^2)になってしまう。ここでは、これを回避したソートを習作してみる。ちなみにC++のstable_sort()だと、安定マージソートをつかってこの問題を回…

平衡二分探索木を使ったsetとmultisetの実装(C#)

C++のsetとmultisetに相当するコレクションをC#で実装してみる。set 順序付けされたデータを重複を排除して保持するもの。C#のSortedSetとほぼ同じだが、lower_bound()とupper_bound()が使える。データの追加・削除・検索いずれもO(logN)。multiset 順序付け…

HackerRank Week of Code 28 参加日記

111位/10432人でレート微増だった。Easy問題は省略する。 https://www.hackerrank.com/results/w28/yambe2002 The Great XOR 整数xが与えられたとき、以下を満たす整数aの個数を答えよ。 a XOR x > x 0 1 例えばx=b10101111とすると、aの候補は b0001nnnn b0…

HackerRank Week of Code - 26 参加日記

398位/6951人でレート減してしまった。いつも数学の問題が多いと順位を落としてしまう。以下Easy問は省略。 Twins 整数iとjがいずれも素数、かつ距離が2のとき、これらをペアであるとする。整数nとmが与えられたとき、区間[n,m]にはいくつのペアが存在するか…

Facebook Hacker Cup 2017 Qualification Round 参加日記

○○×で予選通過。R1は時間的に参加できるかどうか微妙だ。 Progress Pie 進捗パイチャートと点Xがあたえられたとき、Xがチャートの色付き部分に入っているかどうかを判定する。 点の位置とチャートの進捗p(%)を0%からの角度に変換して求めた。 public static …

HackerRank Week of Code - 25 参加日記

25位/7510人の自己ベスト。Hardの1問を正答できたのと、Hard/Expertの部分点を取れたのが大きかった。以下、難易度Easyのものは省略する。 Baby Step, Giant Step 2次元上の座標(0,0)から(d,0)に移動する最小のステップ数を求めよ。ただし、1回のステップで…

HackerRank Week of Code - 24 参加日記

392位/9177人。難易度Hardの「XOR Matrix」が解けそうで解けなく3日ほど苦しんだ(結果は部分正解)。Easy問題は省略する。 Simplified Chess Engine 盤の大きさが4x4、かつクイーン・ルーク・ナイト・ビショップだけが存在するミニチェスを考える。勝利条件は…

ARC049-ARC058+ABC043メモ(練習)

AtCoder Beginner Contest 043 - AtCoder Beginner Contest 043 | AtCoder D - アンバランス / Unbalanced 文字列tについて、tの長さが2以上であり、かつ過半数の文字が同じとき、tをアンバランスを呼ぶ。文字列sからアンバランスな部分文字列を探して、その…

HackerRank Week of Code - 23 参加日記

281位/10162人。たぶん実際の参加者はこの半分くらいか。 難易度Easyの2問は省略する。 Treasure Hunting 二次元平面上の(0,0)地点にいる人が、地点(x,y)にたどり着きたい。彼はおかしなマシンを持っていて、このマシンは①ある地点(x,y)から(x,y)+k(a,b)へ飛…

Topcoder SRM696 参加日記

0完でレート微増だった。Div1のEasyはなぜこんなに難易度が高いのだろう(解けてない人が多すぎる)。Div1 Easy Gperm 頂点数50、辺の数が1~20の無向グラフがある。初期状態では、いずれの頂点も着色されていない。着色には、両端が着色されている辺の数と等…

HackerRank Week of Code - 22 参加日記

457位/12356人。Mediumを1つ落としたのが痛い。いつも数学がネックだ・・・。Cookie Party n人のゲストとm枚のクッキーがある。ゲスト全員に同じ枚数を配るためには、あと何枚クッキーを焼けばよいか。 クッキーがすでに足りているか、足りない場合はゲスト…

AGC003の参加日記

2完で416位/700人くらい。AtCoderのコンテストは問題文が分かりやすくて良い(日本語だからというだけじゃなく)。 A - Wanna go back home 二次元平面上のある点から、1ターンずつ東西南北いずれかに正の距離移動する。ターンごとの方角が与えられたとき、…

Booking.com Back End CodeSprintの参加日記

全完で暫定85位/3075人。Tシャツ貰えるのかな? Destination: Together <3 Jhonはn個の町、Ziziはm個の町を訪れたい。そのうちc個は重なっている。最後に訪れる都市が決まっているとして、二人の希望の都市すべてを訪れる順番は何通りあるか。 訪れる町の合…

Morgan Stanley Codeathon 2016の参加日記

3完1部分点で暫定192位/3601人。数学が分からなくて苦しんだ。 Jesse and Profit ある銘柄のN日分の株価が与えられる。ちょうど利益Diを得るためには、いつ買っていつ売ればよいか。ただし、株を保持する日数は最小化したい。さらに、複数の解がある場合は、…

AGC002の参加日記

AGC第二回。2完397位/662人で惨敗。A - Range Product 整数a,bが与えられたとき、a, a+1, ..., bすべての積の符号を求めよ。 aとbが両方負のときは、個数の偶奇で解が変わる。 if (a > 0 && b > 0) Console.WriteLine("Positive"); else if ( (a <= 0 && b >…

天下一プログラマーコンテスト2016予選Aの参加日記

2完の141位/446人。さっさともう一問解けるようになりたい。A - 天下一プログラマーゲーム 1~100の数のうち、3と5のいずれでも割り切れない数の合計を求めよ。 Console.WriteLine(Enumerable.Range(1, 100).Where(s => s % 3 != 0 && s % 5 != 0).Sum()); こ…

World CodeSprint 5の参加日記

3完+1部分点で暫定349位/6403人。難易度Moderateを1つ落としたのが悔しい。 https://www.hackerrank.com/contests/world-codesprint-5/challenges CamelCase CamelCaseの文字列に、英単語がいくつあるか答えよ。 大文字の数+1を返せばよい。 Console.Writ…

AGC001の参加日記

AGC第一回。参加者1200人超でめでたい。2完で318位でした。 Editorial:https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf A: BBQ Easy - AtCoder Grand Contest 001 | AtCoder バーベキュー用の串が2N本ある。1つの串焼きに2本の串を使う。1つ…

ARC053 - ARC057メモ(練習)

ARC057 A: 2兆円 - AtCoder Regular Contest 057 | AtCoder 所持金がt円ある。ある日の所持金がt円なら、次の日には1+Kt円増えている。二兆円に達するのは何日後か。 やるだけだが、k=0のケースを考慮しないとTLEになる。 public double Solve(double a, dou…

Topcoder Open 2016 Marathon Match(Round 3)の参加日記

制約が多くて面倒な問題だった。そのせいか、レート中位~下位の参加者がずいぶん少なかった。 結果は暫定62位/101人の定位置。問題概要 長さ1の正方形セルSxS個で構成されるマップがある 各セルはタイプ(0~9)が設定されている マップ上にはN個のアイテム…

Topcoder Marathon Match Round90 勉強メモ

2位のEvbCFfp1XBさんのコードを読んでみる。 https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=14094&rd=16495&cr=23100980&subnum=3問題文はこちら。 https://community.topcoder.com/longcontest/?module=ViewProblemStatement…

Topcoder Open 2016 Marathon Match(Round 1)勉強メモ

4位のnikaさんのコードを読んでみる。 https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10729&rd=16702&cr=20315020&subnum=18Forumのご本人のポストによると、次の3つのフェーズに分かれているらしい。パート1(30%) rootが分…

Topcoder Open 2016 Marathon Match(Round 2)勉強メモ

前回の続き。上位者のコードで勉強したメモ。 Psyhoさんのコード http://pastebin.com/GQV4yrDj UFOモードではモンテカルロシミュレーション、TSPモードではGreedyに経路を決めたあとに焼きなまししているようだ。TSP部分だけ読んでみる。→Greedy部分は(実…

Topcoder Open 2016 Marathon Match(Round 2)の参加日記

62位/183人の定位置だった。そろそろ一皮剥けたいものだ。問題概要 二次元平面(1024x1024)に星が100~2000個ある 星の場所に、ランダムに船が1~10隻ある 星の場所に、ランダムにUFOが0~(星の数/100)個ある 1ターンごとに船を動かすことができる 1つのターン…

ベルマンフォード法とダイカストラ法について

メモ。 AOJのこの問題で、入力数が大きいパターンでタイムアウトになっていた。 有向グラフが与えられる。このとき、頂点rから各頂点までの最短経路を求めよ。 単一始点最短経路 | グラフ | Aizu Online Judgeダイカストラではなくベルマンフォードで解いて…

Topcoder Open 2016 Marathon Match(Round 1)の参加日記

結果は55位/136人と振るわなかったが、今後のために記録を残しておく。問題概要 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16702&pm=10729 平面上に、木の幹がランダムに点として存在する それぞれの幹からは、ランダム…

k平均法(k-meansクラスタリング)実装

Courseraの機械学習コースでk平均法を学んだので、理解を深めるために実装してみた。 わざわざ日記にするほど難しくはないが、メモということで。ソースコードはここ。メインは次のGetKMeans_withCost()で、tryNumの数だけk平均法を試して、コスト(最寄りの…

ニューラルネットワーク実装

Courseraの機械学習コースでニューラルネットワークを学んだので、習作としてC#で実装してみた。多層パーセプトロン対応。Classification専用(シグモイド関数をベタ書きしてるので)。 ソースコードはここにおいてある。 実装の概略 ネットワーク各層の関数…

HackerRank Week of Code - 19 参加日記

HackerRankのWeek of Code - 19に参加したのでそのメモ。 結果は346位/3176人だった。 Fix the Cycles 4つのノードA,B,C,Dをもつ有向グラフを考える。D→Aのエッジをa、A→Bのエッジをb、B→Cのエッジをc、C→Dのエッジをd、A→Cのエッジをe、B→Dのエッジをfとす…

線形回帰とロジスティック回帰の実装

Courseraの機械学習コースで多変量線形回帰(最小二乗法)とロジスティック回帰を学んだので、理解を深めるためにC#で実装してみた。 特にロジスティック回帰は、コースで最急降下法の実装をやらなかった(Octave組み込みのfminuc()を使う)ため、練習として…

二分探索の練習

二分探索の練習。 問題は「プログラミングコンテスト」「二分探索」あたりで適当にググったもの。 - UpperBoundとLowerBound CのSTD関数をC#で実装。 public static int LowerBound(int[] ar, int val) { var lb = -1; var ub = ar.Length; while (ub - lb >…

初等整数論の基本の復習

2016/8/20誤記修正基本的な数学がいまいち使いこなせてないので復習しておく。参考にしたのは蟻本と以下のサイト。 http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ ユークリッドの互除法 整数aとbについて、a > b > 0 かつ a % b を r とした…

Topcoder Marathon Match Round90の参加日記

TopcoderのMarathonMatchは、過去3回参加していずれも上位3割くらいの結果に終わっている。よって目標は上位2割。 これまでの反省点まとめ 問題をちゃんと読む 紙と鉛筆で考えてから組む。いきなり実装しない Web等を参考にしすぎない。アルゴリズムは自…

Union-Find書き直し(C#)

C#

前々回のエントリで、Union-Findの効率が少し悪いとコメントをいただいた。確かに、実務上の問題は小さそうだが、このデータの持ち方はイマイチかもしれない。 そこで、次のように書き直してみた。 各ノードにParentとRank情報を持つ 配列ではなくツリー構造…

Topcoderサイトのリンク集

ひどいデザインで有名なTopcoderのサイトだが、本当に目的の記事にたどり着けないレベルになってしまった。 個人的によく使うところをメモしておく。 SRM Match Editorials http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis アクテ…

C#実装(Kruskal法とUnionFind)

C#

クラスカル法(連結グラフの最小全域木を求める)はアルゴリズムがとても分かりやすくて好ましい。参考は例によって蟻本。 ・辺の集合から、最小コストのものを見つける ・この辺が、これまで取り出した辺と連結していなかったら使う。連結済なら破棄 →これ…

アメリカ大手IT企業での就職面談(失敗記)

半年ほど前だが、アメリカの超大手IT企業からスカウトが来て、そのくせ電話面談で落とされるという屈辱的な経験をしたので、戒めとして晒しておく。 4月下旬 LinkedIn経由でリクルーターからメッセージが届く。デトロイトで本社採用SDE(Software Development…

木星をバスケットボールとしたときの星の大きさ

宇宙少年の息子のために、ボールやビー玉で太陽系を作ってあげた。そのときにいろいろ計算した結果を、捨てるのも何なので日記に書いておく。 まず太陽系の恒星と惑星。木星の直系を24cm(大人用のバスケットボールくらい)に合わせると、地球と火星がビー玉…

二次平面のベクトル演算(C#実装)

C#

二次平面幾何の復習として、内積や外積、線の交点などを計算するコードを書いてみた。どこかで再利用するかもしれないのでクラス化してある。 参考にしたのは蟻本とこのサイト。 まず、X・Y座標の保持と、座標用の演算オペレーターを用意する。 /// <summary> /// Pon</summary>…

ダイクストラ法の実装(C#)

C#

前エントリでPriorityQueueが用意できたので、最短経路を解くコードをダイクストラで書いてみた。PriorityQueueを二分ヒープで実装したため、計算コストはO((E+V)logV)になっているはず。 ダイクストラ法 - Wikipedia なお、C#のTupleがIComparableではない…

C#でのPriority Queue(優先キュー)実装

C#

.NETのC#にはPriorityQueueがなくて困るので自作してみた。 二分ヒープを使った実装で、ほとんど蟻本のソースコードそのまま。ただし、次の拡張を行っている。 ジェネリック型に対応 昇順、降順の指定可 カスタムIComparerを指定可 Peek()、Count()、Clear()…

Kyle Simpson「Advanced JavaScript」学習メモ(2)クロージャ

クロージャ 関数が構文スコープ外で実行されても、自分自身のスコープを覚えている機能をクロージャを呼ぶ。 function foo() { var bar = "bar"; function baz() { alert(bar); } bam(baz); } function bam(baz) { baz(); //"bar" } foo(); この例では、baz…

Kyle Simpson「Advanced JavaScript」学習メモ(1)スコープ

Pluralsightの「Advanced JavaScript」(Kyle Simpson)学習メモ。 スコープとJavaScriptコンパイラ JavaScriptのコンパイラは、コンパイルと実行の2つのフェーズに分けられる(実際はさまざまな高速化のためのテクノロジーがあるが、ここでは単純化する)…