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

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

行列計算じゃねとは思ったがそんなあっさり解けるとは思わなくて本番は手を付けなかった。問題: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://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp解法:dp[n]を,「駅がnまでであるとした時、nで止まらないという条件のもとで題意の条件を満たす部分集合の数」とする。すると、まず求める答えはdp[N+1]とすれば良い。また、dp[1]=dp[N]=0となる。こ…

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

補集合を思いつくのに時間がかかった。問題:http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_4解法:「その数を1つでも含む連続する部分列」ではなく、「その数をひとつも含まない連続する部分列」を考え、それを可能な部分列の合計か…