最近ちょっとだけ機械学習を勉強し始めました。教科書には「ランダムフォレストはそれぞれの説明変数の値がどれくらい目的変数を算出するのに重要か」を示す重要度の値を出力を示すことができると書いてあったのですが、pythonではどのようにしてそれを算出…

問題:TopCoder Statistics - Problem Statement解法:座標圧縮した後ダイクストラする。座標圧縮についてはよくわからなかったのでkmjpさんのコードを参考にさせていただきました。 以下ソースコード struct Point { int y; int x; Point() {} Point(int y, i…

問題文を理解するのが一番難しかった。問題:TopCoder Statistics - Problem Statement解法:確率を最大化するためには,なるべくいろいろなフィールドに人を同じ人数だけ分散させるのが良い。そのようにシミュレーションして得られるのが答え。 以下ソースコー…

こういうの苦手。問題:TopCoder Statistics - Problem Statement解法:departure順に客をソートする。で,ある客がまだ処理済み出ない時,その客を処理できる中で最もdepartureするのが遅い客を選択する。この選び方で最適なのは帰納法的に証明できる(と思う)。…

よく考えると別に全然難しくなかった。問題:TopCoder Statistics - Problem Statement解法:数式を適当にいじると,数式のプラスとマイナスは +[--...-][++...+][--...-][++...+][--...-]という形で出てくることがわかる。また,マイナスの区間からプラスの区間…

問題:F: チェックディジット - 東京大学プログラミングコンテスト2014 | AtCoder解法:条件を満たすような関数を考えるために,f(s)=(文字列sについて,s[j] 以下ソースコード set<string> S, SS; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { string </string>…

これに何時間かけたかと・・・問題:B: 交点 - 東京大学プログラミングコンテスト2014 | AtCoder解法:点(a,b)を通るような直線が,整数座標(p,q),(r,s)を通るとすると,直線の方程式は となる。両辺を1000倍すると, となる。これが点(a,b)を通るので ここで,100…

東京大学プログラミングコンテスト2014に参加してきました。結果はAとCが通ってFが微妙な点数になって後適当に部分点とかなり酷い結果でした。辛い・・・問題:E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder解法:Trie木というのがあるらしいの…

うーん、なんか最近方針はあってるけどちゃんと実装するまでがめっちゃ遅い。問題:No.174 カードゲーム（Hard） - yukicoder解法:まずAとBのカードをソートする。解法としては,A,Bがi番目のカードをターンtに出す確率を求めて,それを比べることで答えが求ま…

なんとなく初めて解く部類の問題な気がする。問題:http://codeforces.ru/problemset/problem/525/E解法:数列a[]のn個のうちの最初のn/2個を全探索して取りうる値及びその値を取る場合の数を調べる。次にn/2個からn個にある数を全探索して同じことをする。以…

行列計算じゃねとは思ったがそんなあっさり解けるとは思わなくて本番は手を付けなかった。問題:http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_e解法:条件式を表す行列Aは転置行列が優対角行列になる。計算を反復するgauss-s…

雰囲気あってたけどちゃんとした解法にはならなかった。問題:http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_d解法:雰囲気としては,それぞれの頂点Aについて、C->B->AとなるようなAに向かってくるパスの最大長とA->D->Eとな…

モンテカルロ法が想定解のことあるのかー。問題:http://yukicoder.me/problems/325解法:誤差が結構許容されるのでモンテカルロシミュレーションする。ちょっと気になったので調べたところ、モンテカルロの精度をN倍するためには試行回数をN^2倍しないといけ…

Codeforces Round #297 (Div. 2)に参加しました。C問題を誤読しててそれに大半の時間を使ったためにボロボロでした。問題:http://codeforces.com/contest/525/problem/C解法:できるだけ長い辺と長い辺を組み合わせて長方形を作るのが最適。ということでそう…

SRM654に参加しました。結果はeasyをなんとか解いて(130ptぐらい)、チャレンジを1回成功させて自分にしてはそこそこ良い結果。解法:1個連続になる個数の期待値、2個連続になる個数の期待値、...、n個連続になる個数の期待値を足した和が答え。それぞれの連続…

各チームの勝った回数が決まればそこからある勝敗表を再現することができるということがミソ？問題:http://community.topcoder.com/stat?c=problem_statement&pm=13630解法:自分のチームは当然2勝する。すると、敵チームの数がNであるとすると、残っている勝…

前に同じ発想を使う問題を解いたので近い発想には至れたが、なんとなくコードを提出した後にちゃんとした証明を思いついた。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13625&rd=16278解法:まず数列をソートする。一番大きい数を決め…

なんとなくアルゴリズム的に正しい気がするけど本当にあってるのかがよくわからない。どう証明するのかわかる人いたら教えていただけると助かります。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13595&rd=16279解法: 以下ソースコード…

こっちはやや手間取った。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13606解法:easy問題のようにすべての頂点について高さを2分探索することはできない。しかし、よく考えると、高さが最大の点は、高さ制約がある点の間で山を作れば…

これは簡単なのでコードだけ。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13634&rd=16279 const int INF = 1e9; bool ok(int pos, int h, const vector<int>& x, const vector<int>& t) { if (h > pos-1) return false; int n = x.size(); for (</int></int>…

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13649&rd=16312解法:まず基本として、値段が小さいものから順に買っていくのが最適である。ということで、値段の小さい順に選んでいった時、N番目のものは何かを求めれば良い。 KやNはかな…

問題:http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp解法:dp[n]を,「駅がnまでであるとした時、nで止まらないという条件のもとで題意の条件を満たす部分集合の数」とする。すると、まず求める答えはdp[N+1]とすれば良い。また、dp[1]=dp[N]=0となる。こ…

これわからなかったのちょっと恥ずかしい気がする問題:http://yukicoder.me/problems/414解法:573が素数じゃないので、割り算するのはマズイ。ということで、数え上げをすべて掛け算で済ませることを考える。M個の数列でm1,m2,m3,...,mn個の共通因子がある場…

なんとなく解法は覚えていたがstringとcharの変換周りで悩まされた。問題:http://community.topcoder.com/stat?c=problem_statement&pm=12871&rd=15711解法:下のソースコードのコメントに書いてあるとおり、「dp[n][a][b][k]: n文字中a文字をA,b文字をB,で埋…

ここからしばらくは解き直しphaseなんだけど意外によくわからなかったりするので復習する意義はありそう。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13642&rd=16312解法:題意のペアの数が最大になるのは明らかに,n=N/2としてN-n個Aを…

とりあえず本番部分点取れたのは良かった。満点解法は答えみてなんとなく理解してからもめっちゃ混乱して3時間くらいかかった。問題:http://abc020.contest.atcoder.jp/tasks/abc020_d解法:Kの各gcdの値gごとに(GCD(n, K)=g)となるnの和を計算する。これを満…

時間間に合うように実装したつもりだけどなんか時間かかってる・・・(最悪1.919sとかだった)なんでこんな時間かかるのかよくわからない(多分mapかなとは思っている)ので誰か教えて欲しいです。問題:http://community.topcoder.com/stat?c=problem_statement&…

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13657&rd=16313解法:注目すべき性質は２つ。 ①整数の大小関係はbit数の大きいものを優先に決定される ②整数aとbのk番目のbit数が同じであるとすると、k番目のbitが1の整数cを使ってa = a^c,…

勘が冴えた感じがあって240点取れた。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13656&rd=16313解法:N=(sの長さ)とする。N==Kのときは当然消した文字をすべて特定できる。K Kが成り立つとすると、K文字消しても必ず同じ文字同士の順…

完全二分木であることの必要十分条件が足りなくて何回もWAを出してしまった。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13667&rd=16314解法:どの辺を取り除くかを全探索し、そのそれぞれについて完全二分木になる/ならないを判定する…