凸関数の最大値は精度良く求められるけど、最大値を与える値の精度はよくないというお話。 具体的な問題で考えてみよう。 関数f(x) = x*(1-x)の最大値と、最大値を与える値を誤差1e-9以下で計算しなさい。 もちろん高校数学の範囲で解けて、厳密解はx=0.5で…

keyword 幾何 平面走査法 誤差 数値計算 Java 問題概要 中心が整数座標 in [1,30]*[1,30]、半径1の円柱がある。影の幅が最も大きくなるときの値と最も小さくなるときの角度を誤差EPS=1e-10以下で求める問題。 解法 まず、角度を決めたときの影の幅は比較的簡…

最近eclipse使ってコーディングするようになったけど、自分の貧弱な計算機ではeclipse上でプログラムをコンパイル、実行するのは重くてやってられない。なのでコンパイル、実行は端末上でやることにした(何でIDE使ってるんだっけ)。以下のファイルに適当に名…

keyword 動的計画法 C++ 問題概要 長さN(不定である。不定な部分に[0,M]の値を入れて美しい配列にしたい。何通りあるかをmodで求める問題。美しい配列とは次の2条件を満たす。 どの連続する3つも狭義単調減少でない。 a[i]の値はa[0],...,a[i-1]の相加平均以…

問題概要 あなたのスコアは最初0.0です。スコアにa(-2.0 解法 a,bがそれぞれ正負の場合とbについては1より小さいか大きいかとか考えて場合分けで書いたのが以下のコード。Acceptはされたけど、こういう場合分けを書きまくるのはミスを誘発して良くない。計算…

keyword ハッシュ C++ 問題概要 長さM( 解法 テストケースが多いらしく、TLEと戦わなければいけない。mapに突っ込んでいけばO(M*N*log N)で解けるけど、mapは定数が重いので落ちる。vectorに突っ込んでソートする方法でも(vectorをreserveしたにも関わらず)…

keyword 動的計画法 Java 問題概要 風船がN( 解法 見た瞬間にDP。多分一番楽なのは状態をdp[i番目の風船][搭載している風船の個数]とする。計算量O(N)。dp[座標][時間][風船の個数]とやっても解けるかもしれない。意味ないけど。実装時間17分。

keyword 探索 Java 問題概要 ノード数V( 解法 探索するだけ。グラフを構成する部分が面倒くさい。実装時間13分。

以前に使っていたテンプレートとかマクロとか。 最近は誰にでも読めるコードを書くことをこころがけているので全然使っていないけど。 どうしようもなく間違っているコードが撃墜すらしてもらえないのは少し悲しいし(コードが汚いと言われている様に感じてし…

keyword ハッシュ 定数倍最適化 C++ 問題概要 長さM( 解法 ICPC的には、編集距離2以下の文字列を全部作って、カバーされるかどうか確かめればよい。カバーされるかどうか確かめる部分は、Lが一定なことを利用してRabin-Karpっぽくローリングハッシュでハッシ…

keyword BIT C++ 問題概要 a*b = rev(a)*rev(b)となる(a,b)をluckyな組と呼ぶ。このとき、[1,X]*[1,Y]内にluckyな組がW( 解法 肝はa/rev(a)=rev(b)/b。あとはxの小さい順にBITに値を加算しながら、二分探索でx*y>=Wを満たす最小のyを探す。計算量は大体O(Max…

解法 実装するだけ。スペースを消去できるのはmessage間だけ(text間ではない)ことに気づかなかったけどcodeforcesにしては珍しくpretestで弾いてくれた。

解法 3の累乗を計算するだけ。n=0に注意。 感想 最初は数列辞典に投げようと思ってた。それと新しいコンテスト用の環境(eclipse CDT + ファイルが更新され次第コンパイル->サンプルケースの実行をする補助スクリプト)が無事に動いたので安心。

keyword ハッシュテーブル C++ 問題概要 N( 解法 前の記事にしたがってそのまま実装する。メモリ制限が64MBのとき確保できる32bitの配列のサイズは2^23が目安。安全を取って今回はサイズを2^22とした。このとき、特定のひとつのハッシュ値が衝突する確率はN/…

衝突の問題さえ回避すれば非常に優秀なデータ構造である。 弱点はメモリを大量に消費すること。メモリの局所化とは対極であること。for_eachみたいなことができない。STLにない(tr1とかextとか__gnu_cxxとかはさておき)等。 そもそもsetやmapと計算量がlog程…

keyword Rabin-Karp ハッシュ Java 問題概要 W*H(W,H 解法 気分的にはRabin-Karpに近いことをする。ただし、Rabin-Karpを真面目に実装すると、全て一致するときに計算量がO(W*H*p^2)となってさすがにこれは間に合わない。なので手抜きでハッシュ値の一致だけ…

keyword 最大流 二分探索 C++ 問題概要 K( 解法 最大値の最小化なので定石通り二分探索する。距離の上限を決めてやると2部グラフが構成できるので、あとは2部マッチングのようにsourceから牛へ容量1の辺を張り、搾乳機からsinkへ容量Mの辺を張ってやればよい…

解法 素材を組み合わせて新しい素材を作るアレ。1種類しか変化させないし、サイズも小さいので特に計算量を減らしたりする必要はない。問題文を読み間違えていたけど、ただのシミュレーションらしい。 感想 計算量を減らす工夫はいらないけど実装量を減らす…

keyword 尺取り法 C++ 問題概要 長さN( 解法 尺取り法で部分列における出現回数を記録しておき、ちょうど1回だけ表れている数はsetに突っ込んでおけば最大の数が対数時間で取り出せる。計算量O(N*log N)。 追記：よく考えたら部分列の長さが一定だし尺取り法…

解法 状態数が400^2で、ある状態からの遷移が20通りなので普通にメモ化探索するだけ。反射は打ち消せるので無意味。 感想 状態数が微妙に少なかったのと配列のindexを座標で持っておくのが面倒だったのでmapでメモ化した。もちろん座標を平行移動して普通の…

解法 特にアルゴリズムというほどのものは無い。

解法 for文を習いたての人のための例題。

keyword 動的計画法 C++ 問題概要 K( 解法 aの小さい順に積み上げればよいことに気づけば簡単。小さい順に、到達可能な高さを配列で持っておけばよい。一応通した解法では計算量がO(K*log K + K*MAX_A*MAX_C)で通った(実装時間8分)けど、無駄が多いのでもう…

keyword 2部マッチング C++ 問題概要 H*W(H 解法 重なる部分を最小化すればよいことが分かる。ということで、隣接する*同士に辺をはった2部グラフの最大マッチング+マッチングで覆われていない頂点の個数が答えとなる。 感想 最近オンラインジャッジをだらだ…

keyword 座標圧縮 segment tree C++ 問題概要 a,b(0 解法 座標圧縮してsegment treeに突っ込む。区間に対する更新処理と点に対する最大値が求められればよい。segment treeの部分は蟻本を参考にして書いた。segment treeの配列のサイズを勘違いして通すのに…

keyword RMQ C++ 問題概要 長さN(区間で最頻値が何度表れるかというQ( 解法 まず、数列が単調なので連続する同じ数を調べる。例えば、{-1,-1,1,1,1,1,3,10,10,10}は新しい数列x={2,4,1,3} に変換する。そしてxの累積和も持っておく。クエリp,qに対して、p,q…

解法 リハビリがてら。やるだけ。

問題概要 N( 解法 時計回りと反時計回りは別々に考える。とりあえず時計回りだけ考えよう。c[i]を、0からスタートしてiにたどり着くのにどれだけ燃料が余るか(正負を込めて)、とする。このとき、cの最小値をアテインするようなiをスタート地点として選べる。…

問題概要 n( 解法 n=2は解なしであることに注意。 すぐ思いつく解法：素数を小さい順にp[0],...,p[n-1]ととってくる。a[i]=(Πp[k])/p[i]とする。本番中は10^100を越えてしまうような気がして書かなかったけど、そんなことは無かった。 賢い解法：a[0]=10, a[…

解法 やるだけ問題なんだけど番兵を置かずにやったら大分時間をとられた。やっぱり例外処理は苦手。