10位だった。

3日目の作問を @k_operafan さんとしたのでメモ。 主に自分の作問について。 解説は無いのであしからず…。 自分が作った問題の解説を挙げました。 https://www.dropbox.com/sh/ingo41xpnd6fuoi/5-8HaPoOhK/aizu_camp_2013全く推敲していませんので、多分適当…

こう考えられたらいいなぁというメモ．どちらもある条件を満たすまでの手数を最小化する問題． GooseTattarrattatDiv1 各iについて"s[i] = s[n-1-i]"となっていることが条件． 状態ベース "s[i] = s[n-1-i]"という条件から，対応する文字は必ず同じ文字に変…

割りとメジャーだけど点連結度の計算方法． 辺連結度 u-v間の辺連結度は，「消すとu-v間が非連結になる辺集合の最小サイズ」． これは，u->vの最大流に一致． 点連結度 uv間の辺連結度は，「消すとuv間が非連結になる頂点集合の最小サイズ」．「点連結度 下…

http://jag2013spring.contest.atcoder.jp/tasks/icpc2013spring_f を解いたので，2次元FFTのやり方． 1次元FFT まずは，離散フーリエ変換を． 数列 f(0), f(1), …, f(N-1) に対するフーリエ変換は， ※の中の符号が逆だったりする事も有るけど問題無い． 逆…

全体の流れは[id:k_operafan:20130704:1372908597]を参照下さい．ここでは，自分の反省．何か思い出したらまた書きます． コンテスト中について 読んだ問題 A,B,C,E ※Bは説明が理解できなかったのでizさんにお願いしました． コーディング A 考察がまとまれ…

Integer同士を=で比較すると変な現象が起こります． ArrayList<Integer> list1=new ArrayList<Integer>(asList(1, 128)); ArrayList<Integer> list2=new ArrayList<Integer>(asList(1, 128)); System.out.println(list1.get(0)==list2.get(0)); System.out.println(list1.get(1)==list2.get(1)); </integer></integer></integer></integer>…

プログラミングコンテストにてハマったことのある罠をご紹介します． PriorityQueue.removeについて．あまりハマることは無いですが，PriorityQueue.removeの計算量はです．うっかりだと思って書くと死にます．

プログラミングコンテストにてハマったことのある罠をご紹介します． ArrayList.removeについて．ArrayListは隣接リストなどに使いますが，removeをすることがたまにあります． remove(int index) index番目のオブジェクトを削除して詰める． remove(Object …

プログラミングコンテストにてハマったことのある罠をご紹介します． Mapについて．使う頻度の多い，Map.containsKey(Object)とMap.containsValue(Object)． これらは，引数がgenericsに対応していないため，うっかりしていると変なオブジェクトを引数にして…

実線の長さが入っている．点線は考慮しない．dp(i,j)を[i,j]での答えとすると， v = dp1(i,r)+dp2(r,j)として， dp1(i,j) = v+x[j-1]-x[i] dp2(i,j) = v+y[i]-y[j-1] dp(i,j) = v+x[j-1]+x[i]+y[i]-y[j-1] となるrがある．dp1(i,r)+dp2(r,j)が暫定最適値より…

多項式を区分的線形関数で近似する問題．お気に入りというわけではないが，ちょっと面白かった．便宜上，求める関数を [tex:g(x)=\begin{cases}a_1(x-c)+b & (xc) \end{cases}] とする． をどうにかしたい．ポイントは，2つ． bを決めるとa1とa2は独立に求ま…

EfficientなSolutionを思いついたのでメモ．条件を満たす点群（黒点）はこんな感じになる．各点を結んだ線分の左下か右上かを判定出来れば良い． y=-xに各点を射影すると諸々の処理が簡単にできる． 新しい点Pを追加 y=-x上での両脇の点を結ぶ線分より左下な…