2016-10-01から1ヶ月間の記事一覧
10/17 imulan.hatenablog.jp ARC 021 C - 増築王高橋君 まず、個の家に対して、どこまで増築していいか値段を二分探索する。が大きいので、それぞれの家に増築の回数を1回ずつ余地を残すために回以下の増築が許されるところを探索して、それがおわったらそこ…
問題 2429 -- GCD & LCM Inverse 問題概要 の値と、の値が与えられるとき、の値を答えよ。ただし候補が複数ある場合には、その中でもが最小のものを答えよ。 アイデア まず、基本的な性質としてがある。両辺を2回で割ると となる。これらは全て当然割り切れ…
問題 Minus One | Aizu Online Judge 問題概要 頂点辺の無向グラフと頂点番号が与えられる。この無向グラフに辺を1つ足すことによって、もとのグラフにおけるからへの最短経路長よりも1だけ短くすることができるようなは何通りあるか。 からへはたどり着ける…
問題 SPOJ.com - Problem METEORS 問題概要 ある惑星の軌道上には隕石が降り注いでくる。その軌道を個の領域に分割し、と番号をふる。このとき、番号は連続的に振られ、番目の領域と番目の領域は繋がっている。その個の領域に分けた領域に対してそれぞれつず…
10/1 CF 721 C - Journey 方針自体は(現在地,訪れた超点数)=かかる時間の最小値というシンプルなDPだったのだけど、queueとBFSで実装してしまい本番はMLEで死んだ。dfsに書き直して様々な修正をしてようやくできた(submission)。 CF 721 D - Maxim and Array…
問題 TopCoder Statistics - Problem Statement 問題概要 AliceとBobが次のようなゲームをする。まず、正の整数が与えられる。次に、Aliceは正の整数を選ぶ。最後に、Bobは~の順列を作成する。 そして、の番目の要素をと表すこととし、関数を次のように定め…
問題 D: ~K Perm Counting - AtCoder Grand Contest 005 | AtCoder 問題概要 長さの順列がある。について、を満たすような順列は何通りあるか、答えを (素数)で割った余りを求めよ。 アイデア 答えを直接求めに行くのではなく、余事象を求めることにする。つ…