頑張る。 全面と側面で同じ形であることを知らなくて無駄にコードを書きすぎた。 #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> using namespace std; int X[2][5]; int Y[2][5]; int L[20]; int R[20]; double EPS=1e-9; int ABS(int a){return max(a,-a);} int mai</math.h></vector></algorithm></stdio.h>…

幼稚園児でも解けるような問題だった。具体的には、 A=Bの時 山が一つでA>Bの時 山が一つでA たくさん山があり、A,B>>石の個数の時 を考えてみれば自然と答えは見えてくる。 #include<stdio.h> #include<algorithm> using namespace std; int p[110000]; int main(){ int n,a,b; </algorithm></stdio.h>…

上手いこと探索。 半分全列挙をmap DPで早くしたらオーバーキルみたいな感じになってしまった。上手いこと探索系は苦手なのでしょうがない。 #include<stdio.h> #include<algorithm> #include<map> #include<string.h> using namespace std; char in[20]; map<int,int> dpL[8][3][71]; map<int,int> dpR[8][3][71];</int,int></int,int></string.h></map></algorithm></stdio.h>…

AOJに戻ってみた。知識ゲーだと思って解説読みましょう。こんなDPは他に見たことがない。 実装はそこまできつくない。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int p[610]; short dp[2][610][180010]; short rev[2][610][180010]; int dist[180100</vector></algorithm></stdio.h>…

待ち受ける大きな罠 (誤差)に気を取られていると足元(添え字)がおろそかになるんじゃ。 #include<stdio.h> #include<algorithm> #include<math.h> #include<vector> using namespace std; long double x[110]; long double y[110]; long double r[110]; const long double EPS = 1e-20; const lon</vector></math.h></algorithm></stdio.h>…

PCK2014本選の問題が今までFrameしかなかったが、最近他も追加されたので全部解いた。 0305: Yuekis' Audio Room やるだけ。 #include<stdio.h> #include<algorithm> using namespace std; int main(){ int a;scanf("%d",&a); while(a--){ int r,t; scanf("%d%d",&r,&t); if(r%10</algorithm></stdio.h>…

典型面倒データ構造。クソ。 各ステップに面倒要素が搭載されており、やる気を的確に削いでくる。というかこういう問題で何やっても通るようなサンプル置くのは何なの……Starry Sky木の更新条件をすっかり忘れていた。 #include<stdio.h> #include<algorithm> using namespace std</algorithm></stdio.h>…

0差、1差、2以上差の3つに分けて全探索。 言われてみればなるほどという感じだし、このくらい思いつくべきでは…… #include<stdio.h> #include<algorithm> using namespace std; char in[10][10]; int pl[10]; int u[10][10]; int t3[10]; int q[10]; int used[10]; int L; int df</algorithm></stdio.h>…

Heavy-Light Decomposition + 遅延評価 Segment Tree (しかも、区間和、左端からの和の最大値、右端からの和の最大値、区間の中での連続する和の最大値の4種類を持たないといけない)。 めちゃくちゃ重いが、特に大きなバグなく通すことができvery good. #inc…

右手法だか左手法だかいうやつ。双対は作る必要がないが、だからと言ってそんなに楽というわけでもない。 これ結構面倒なのに41人も解いているのもすごいし、3300B台で短いほうから2番目というのもすごい。 #include<stdio.h> #include<algorithm> #include<math.h> #include<vector> using names</vector></math.h></algorithm></stdio.h>…

dp[v]:= v以下の部分木と同じ形が何手で作れるか それぞれに対してコピペに使う根を全探索(サイズの制約で無理なのは無視)して判定。 ハッシュで同じ形を2回以上探索しないようにする。誰か計算量を解析してください。 #include<stdio.h> #include<algorithm> #include<map> #include<vector> </vector></map></algorithm></stdio.h>…

ネタバレ：Minimum Cost Flowは必要なかった。全部 ai > biのときは、分岐するのが無駄と分かるので最短路。 ai ↑の流量の候補は実は定数個らしくて決めうちを上手くやればWarshall-Floydでも余裕らしい。なるほどね。サンプルが異常に弱くて ai #include<stdio.h> #i</stdio.h>…

辺と辺の間をn等分 (n=1,2,...,7)した点を全部列挙してまたもや最短路。ただ闇雲に重いだけ。(量だけなら1000の中ではかなり重いほうだと思う。) #include<stdio.h> #include<algorithm> #include<vector> #include<queue> #include<math.h> using namespace std; char in[3][3][4]; int DIV=3; int gcd(</math.h></queue></vector></algorithm></stdio.h>…

教育的良問。是非解くことをおすすめします。まず、一般グラフの完全マッチングの存在判定におけるTutteの定理を説明します。 Tutteの定理とは、無向グラフから作られる|V|×|V|のTutte行列((i,j)間に辺があるときはA[i][j]+A[j][i]=0となるように変数を、辺…

何かAOJ-ICPCの高難度を解くのが流行ってるらしいので流行にのる。Aho-Corasickで判定はできるんだけど、全部を一つ一つ列挙していると間に合わないので、変な順番で枝刈り探索する。 うーんなんか微妙な問題…… #include<stdio.h> #include<algorithm> #include<queue> #include<string> #include<set></set></string></queue></algorithm></stdio.h>…

2016年になってしまい仕方なく解いた。 と思ったら拍子抜けするほど簡単だった……ええ何これは……。 まあ確かに点列挙して最短路みたいな幾何問題は無限に練習したしなあ……。 #include<stdio.h> #include<algorithm> #include<math.h> #include<vector> #include<queue> using namespace std; const double</queue></vector></math.h></algorithm></stdio.h>…

この記事は、AOJ-ICPC Advent Calendarの記事です。 何か名前の"Extreme"ってところがDDRっぽい。 幾何パートは微小なので、本質は枝刈り探索です。選択肢が一番少ない頂点を選ぶ、その中では影響する頂点数が一番多い頂点を選ぶ、次数2以下の頂点を無視する…

この記事は、AOJ-ICPC Advent Calendarの記事です。 まず、文字一つ一つを頂点としたグラフだと思って2つの隣り合う文字にたいして辺をはります。重複辺はつけなくていいです。 このグラフに辺を付け足す必要があれば付け足してオイラー路を作ってやるという…

この記事は、AOJ-ICPC Advent Calendarの記事です。右下の点を軸にして線分を転がすのを実際にシミュレートしていきます。次のケースに嵌りました。 ・とがっているケースでは、反対側の頂点が次の軸になるような場合がある。 ・↑のケースにおいては、x座標…

この記事は、AOJ-ICPC Advent Calendarの記事です。 古い問題らしい癖問。 妙にやりにくい幾何パート、妙にやりにくいグラフパート、そしてそれらに劣らないほどのやりにくさを誇る入力形式。 無駄に大変だけどなんとかはなった。言われたとおりに実装すれば…

この記事は、AOJ-ICPC Advent Calendarの記事です。 余ったところと足りないところの間にDAGのとおりに辺を貼り、最小費用流。 オーダーとしては同じはずの「最小流量制約つきフロー流すだけ」ではTLEするのでなんだか気に入らない。 #include<stdio.h> #include<string.h> #inc</string.h></stdio.h>…

この記事は、AOJ-ICPC Advent Calendarの記事です。 円全体を考えるより、中心の動ける範囲を考えたほうがやりやすい。 中心が動ける範囲は、たくさんの円の積集合。これの境界線上で中心を動かして、長さをもとめていく。この集合上でとがった場所に中心が…

この記事は、AOJ-ICPC Advent Calendarの記事です。 軌道は線分と円弧からなる(円弧は自分で計算する必要がある)。少し考えると、始点と終点からminとかを使ってGreedyに各線分の端点における最大速度が決められることがわかる。 あとはそれに基づいて所要時…

この記事は、AOJ-ICPC Advent Calendarの記事です。 強連結成分分解をする。それぞれの強連結成分には2パターンある。何度でも強連結成分内の好きな頂点にいけるやつと、1点しかなくてしかも自己ループすらないやつ。 後者は0-1、前者は好きな回数使えるナッ…

この記事は、AOJ-ICPC Advent Calendarの記事です。 二つのスポットライトを選んで、いる辺が変わるタイミングを列挙してソートしてして頂点求めて…、というのが面倒だが、そこまでやったら三分探索で距離はわかるし、二つのスポットライトの関係性が分かっ…

選手時代の参加記はここですスクリーンキャストをしようと思ったので、4年前に解いたセットをもう一度といてみました。スクリーンキャストはここです前回に比べて6の方針がすっきりしたと思います。1: (01:28) #include<stdio.h> #include<algorithm> using namespace std; int m</algorithm></stdio.h>…

中心を移動させる一般的なテクにより、円が障害物で点が動く問題となる。 円と円の交点、点たちからの接線、円と円の共通接線を求めて最短路。移動可能性が本質。sAPの仕様がよく分からなくて時間を無駄に使った。本当に練習不足である。 #include<stdio.h> #include<math.h> </math.h></stdio.h>…

たまにはAOJ-ICPCではないAOJを解くことで良問が残っていることを思い出す。ループがあると、そこを1周することで場所を変えずにxor値だけを変えることができるので、これらのループのxorを全部列挙して基底を求めればよいが、 これはxorの性質上、dfs木を作…

構文解析+多項式ユークリッドの互除法。美しすぎるソースコード。 #include<stdio.h> #include<algorithm> using namespace std; long long ABS(long long a){return max(a,-a);} long long gcd(long long a,long long b){ a=ABS(a);b=ABS(b); while(a){ b%=a; swap(a,b); } retu</algorithm></stdio.h>…

動く人の方が速いので立ち止まるのはもったいないみたいな考え方は典型だけどそこまで頻出という訳でもない気がする。当たり前レベルの考察ではあるけれど。 気になる点は4点くらいしかなくて全部を二分探索で求めればよい。噂のテストデータ不備は特に嵌ら…