だいぶ想定解まで迫ったもののO(N^4)から落とせず、解説を見てしまった。 桁数でまとめる発想がなかったのは頭悪すぎたので反省 typedef long long ll; #define MOD 1000000007 const int SIZE = 100100; ll inv[SIZE+10],fac[SIZE+10],facinv[SIZE+10]; ll …

ケーキの端にイチゴが乗ってる時(sample1)の対処をメモ。 len(Y)は片方を(0,Y)に固定したときに等分できる右側の部分の長さを返す関数。 ただ、(0,Y)にイチゴがあると色々面倒なので+eps,-epsの２つに分けて処理した。 誤差怖かったけど通ったので良かった(…

個人的にハマるポイントが山ほどあったので戒めのメモ。 まず、自分のライブラリはverify済でも信用してはいけません (まぁこれはverifyした後にちょっとわかり易くしようと書き換えた自分が悪いのでなんとも言えませんが) (でもまさかadd_edgeが間違ってる…

良問DPとして有名な箱根駅伝。結構考えましたがわからず解説を読んでしまいました。 JAGの解説が少しわかりにくかったのでここにまとめておきます。 順位表の'-'は確定するので無視します。 現在の中継地点の順位表を1位から順に見ていって、前の中継地点で…

予選終わったけど去年の予選一人でやってみました。 今年よりも少し難易度高いかな〜と思った1〜6真にやるだけなので省略 7 更新が一点にしか来ないから普通にsegtreeで数えてあげればイイ #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P; #defin</int,int></algorithm></cstdio>…

有向グラフが与えられるのでそれがオイラーグラフかどうか判定する問題。 無向の時はすべての頂点が偶数であればいいが有向グラフのときはすべての頂点で入次数と出次数が等しければ良いらしい。この際まとめておくと 無向グラフがオイラー閉路を持つ ⇔ すべ…

二人の座標を(a,b),(c,d)とする。(ただしa すべての円について、二人を結んだ線分と交点があるか判定する。 i)a=cの時 適切に処理してあげる。 ii)else 円の中心を(p,q),半径をrとする。 二点を通る直線の方程式はy=(d-b)/(c-a)*x+(bc-ad)/(c-a); 傾きをm,y…

にぶたん。中の操作はsegtreeでごにょごにょする。O(NlogN^2) 前回やったときはわからなくて答え見たけど今やってみたら割と簡単だった。 int n; const int SIZE=1<<19; P seg[SIZE*2]; struct segtree { segtree() { for(int i=0;i<SIZE*2;i++)seg[i]=P(0,0); } void update(int k,int x) { k+=SIZE-1; seg[k].fi=x; seg[k].sec=k-(SIZE-1); while(k>0) { k=(k-1)/2; seg[k]=m</size*2;i++)seg[i]=p(0,0);>…

とりあえず本選5番を2つ倒しました。 まずはBug Partyから。 解法 問題名が縁起悪いですね（笑） … … 実際バグらせまくりました（汗） と同時に重大な勘違いに気づくことができました。 K匹同時に入れられるかどうかで二分探索します。 同時に入れられるかを…

ここ数日幾何にハマっています。これはこの前本番で解けなかった問題。本番では全点間の距離の最大値で間に合うんじゃね？とか思って愚直な解法でやってTLEしてました(それでも22/24も通ったw) 久しぶりに問題を眺めてみると、コレこの前勉強したやつじゃんw…

ACAC002にでたら結果がひどかった…（2完）途中までしか参加しなかったとはいえひどい… こどふぉはやっと青に戻しましたがスタートラインに戻ったという感じです… 早くDiv1に行きたい… 解法 途中までトッピングの値段がすべて同じだという事に気づかず、普通…

解法 まず全店舗からダイクストラして、最寄りの店までの最短距離(dist[i])を求める。 L[i][j](iとjを結ぶ道の距離)>abs(dist[i]-dist[j])ならばその道上の最も遠くなる場所までの距離は max(dist[i],dist[j])+(L[i][j]-abs(dist[i]-dist[j]))であるから、そ…

AOJのArchived Classic Algorithm Contest 001というコンテストが今日あったようです。 僕は出なかったのですが、問題を見て解いてみると1つもWAを出すことなく全完できました（めっちゃうれしい）やたら嬉しいのでソース載せます。 A 繰り返し2乗法。やるだ…

実質初投稿です。 AOJのsolved数は現在141。今はJOI予選までにVol5全完を目標にしています。 解法 W,Hの値が大きいので座標圧縮をする。 それはすぐわかるのだけど、実装しながら大量のバグを埋め込んだせいでいままでずっと解けていなかった問題。 長方形の…