古いJAGの問題はAOJ-ICPCにも載っていないから、隠れた良問みたいなものもある。ということで記事にする。 長方形の下から上にてきと～なルートで行きたい。障害物がN個長方形の中にある。経路中でのこれらとの距離の最小値を最大化せよ。解法 二分探索する…

dp[i][j][k]: [i,j]を文字kにできるか、でDP。 言われてみれば確かになあという感じだし、問題の自由度の低さ的にもこれしかない、という状態の持ち方だから、気がつけるとも思うんだけど絶妙だなあ。 あと、結構このオーダーが重いのとこの後のおまけDPもオ…

ついにdiffを埋めた！かつてのPCKの最終防衛幾何によくあった、ライブラリの強さが大事な問題。 強力なライブラリでごり押しがきくので、思ったより楽だった。行きたい区画は線分とするとよい。経由する点で最短路を求めて、点からその線分に行くということ…

いろいろあわせ技。問題文が複雑だけど(というか英語読んでないんだけど)どうやら、 ・方程式を解けばちゃんと解は一意になる(rankあまる) ・オーバーフローは、long longを使いつつそのつどgcdで割ったら問題ないということらしい。 ということで構文解析し…

前半パートは解説参照。 多項式でできます。 dp[i][j][k][l][m]: i段目、Sがj列、Kがk列にいる。1個前のときSはl列に居た。満たすべき条件二つはmで管理。場合わけが多すぎてかなり大変。 #include<stdio.h> #include<algorithm> using namespace std; char str[12][12]; int dp[</algorithm></stdio.h>…

ブログに記事を書きます Advent Calendar 2014 - Adventar試験がやばくて時間がないからこれで許して。 #include<stdio.h> #include<algorithm> #include<queue> using namespace std; int dp[12][12][12][12][52]; int v[12][12][12][12][52]; int t[12][12]; struct wolf{ int cost; i</queue></algorithm></stdio.h>…

ブログに記事を書きます Advent Calendar 2014 - Adventarに記事を書きたいのに問題を解く暇がないので、過去のをひっぱりだすということにしました。ということでSolveMe。X,Y,ZのうちX,Zをまとめられることは自明だと思います。コードで実験して実はX,Y,Z…

ブログに記事を書きます Advent Calendar 2014 - Adventar13日目。 許すまじ物理ゲー。せめて公式くらい書かないと単なる出題ミス。 そしてそれに加えてYes/Noによる難デバッグ化と変な罠ケースで本当に嫌がらせのために問題作ったとしか思えない。 難易度は…

これはブログに記事を書きます Advent Calendar 2014 - Adventarの12日目の記事です。 天啓DP。 真ん中の正方形区画から外側に向かってDPすることに気がついたらあとは超絶面倒な遷移を作ってDPするだけなんだけど、それに気がつかないから1200+なわけでして…

ブログに記事を書きます Advent Calendar 2014 - Adventarの11日目の記事です。回すだけ。まわしましょう。あと、180度系は面倒なので最初に座標を回しましょう。あとで戻しましょう。 あんまり実装の仕方がよくなくてepsを2種類使う羽目になった。 #include<stdio.h></stdio.h>…

ブログに記事を書きます Advent Calendar 2014 - Adventarの10日目の記事です。成し遂げました。メインの部分の実装は、 基本的に平面走査。 ・新たに分かれるときに挿入する。 ・交差するときに中身を替える。 ・合体するときに削除し、Union-Findで合併す…

この記事もブログに記事を書きます Advent Calendar 2014 - Adventarの記事です。 解説はHziwarAのask.fmもしくはtwilog参照。 ここまでad-hocらしいad-hocなフローは初めてみた。ということで1000AC達成！ #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using names</queue></vector></algorithm></stdio.h>…

ブログに記事を書きます Advent Calendar 2014 - Adventarを切らさないために強引に記事を書いています。やるだけ。これだけたくさん解いていてもまだやるだけが残っていた。1000ACの希望が復活してきた感じがする。 #include<stdio.h> #include<algorithm> using namespace std;</algorithm></stdio.h>…

ブログに記事を書きます Advent Calendar 2014 - Adventar7日目。 最小費用流はBellman-Fordを1回やって流量くらいの回数Dijkstraをするらしい。 また、Bellman-Fordはうまくトポロジカル順に行うとよい。と、最小費用流に関する理解を深めた(といいたいが、…

今日もブログに記事を書きます Advent Calendar 2014 - Adventarやります。これは6日目です。 発想は3ステップ。まず適当に凸多角形を書く。v{i-1}とv{i+1}を結ぶ直線と中心からviを結ぶ直線は直行させたほうが面積が大きくなる。ということで最初の角度を決…

これは ブログに記事を書きます Advent Calendar 2014 - Adventar の4日目幾度となく汚い言葉を発しながらも何とか書き上げて通すことができました。 何とかして上手くデータもって気合で枝を刈るだけ。 #include<stdio.h> #include<algorithm> #include<map> using namespace std; ch</map></algorithm></stdio.h>…

ブログに記事を書きます Advent Calendar 2014 - Adventarの3日目の記事です。 行きたい場所のx座標について、最もy座標が小さいときと最もy座標が大きいときの間に行きたい場所のy座標があればOK.前者は自明。後者を考える。まず、放物線の式になおす。 そ…

ブログに記事を書きます Advent Calendar 2014 - Adventar に参加します。これは1日目です。解のパターンは二つあるので、両方とも試します。桁ごとに試していけばだいたいO(N^2)くらいでおわります。 #include<stdio.h> #include<algorithm> using namespace std; long long b[1</algorithm></stdio.h>…

いかにもJOIerが得意そうな問題。高校生に戻った気分になって書いてみた。 平方分割すればよい。実装時間20分。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int SQ=400; struct wolf{ vector<int>v; int m; wolf(){ v.clear(); m=99999999; } }; vector<wolf>li;</wolf></int></vector></algorithm></stdio.h>…

過去に二度挫折しています！！！ 三度目の挑戦です！！！それっぽい点を全部列挙してそれぞれの頂点に行くことができるか判定。 判定は、途中の点でさえぎられたら駄目、外に出たら駄目というのを判定する。 前者は線分の端点以外で交わるのを判定すればよい…

通せば正義。幾何をする気が起きなくても通る。 #include<stdio.h> #include<math.h> #include<algorithm> using namespace std; int b[12]; double p[12]; double q[12]; double PI=acos(-1.0); int main(){ int x,y; int a; scanf("%d%d%d",&a,&x,&y); scanf("%d",&a); for(int i=0;i</algorithm></math.h></stdio.h>

タイトルがタイトルなので11/1の午前中に解いておこうと思い、解いた。解法：実装するだけ。650とは思えない。空白マスがあんまり多くないことが大事。 #include<stdio.h> #include<algorithm> #include<queue> #include<vector> using namespace std; char str[20][20]; int dx[]={1,0,-1,0,0};</vector></queue></algorithm></stdio.h>…

たぶん問題文の解釈はこうが正しいです。ここら辺のeps周りが全く推測不能なのですが無視していいっぽいです。

問題文： http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171概要：書けや、ゴラァ解法：書く。 現役時代にHuziwaraにとんでもないやるだけクソ問と言われてたのでやったが、意外と適切な実装をすると特に努力しなくても1000B切れる。やったこ…

DPの練習によさそうなやつ #include<stdio.h> #include<algorithm> using namespace std; long long dp1[5000][5000]; int dp2[5000][5000]; long long b[5000]; long long c[5000]; int main(){ int a; scanf("%d",&a); //while(~scanf("%d",&a)){ for(int i=0;i</algorithm></stdio.h>

そろそろKUPCなのでKUPCの過去問をやりました。KUPCは特殊形式の良問みたいなのが多くてgood. UTPCよりもいい問題かもしれない。E: Fpx Number だめなものを数える。 だめな数nは、 素数の2乗の倍数である必要がある。(p^2とする) pより小さい素数qにたいし…

x座標をソートしてそれぞれに対してy,zの幅を求めて数値積分をする。 断面積はせいぜい2次式なので近似公式だけで近似どころか正しい値になる。二つの多面体が面で接したりするといろいろと面倒だったりするので、それぞれのxに対して-EPS,+EPS両方用意して…

！！！これは国内予選のC問題です！！！面倒な探索するだけの圧倒的国内予選感。 僕はこういう変なのより構文解析を出してほしいです… mapでDPと距離で遠すぎるときで枝刈り。 #include<stdio.h> #include<algorithm> #include<set> #include<map> using namespace std; struct snuke{ int </map></set></algorithm></stdio.h>…

りんごさんの締まっていこうの解説(のアーカイブ)がCodeforcesにあるのでそれを読みましょう。 OpenCupの時に言ってた解法がメインパートで簡単。 しかし、DPパートが結構面倒です。 結構時間がかかったが一発ACがもらえたので満足。 #include<stdio.h> #include<math.h> #inc</math.h></stdio.h>…

WFも近いし最近あんまり構文解析やってないから今日は構文解析。 問題文のBNFに解法が書いてある系問題。実数倍の存在を忘れないように。 あと手元だとスタックサイズ調整してやらないとsegmentation faultしました。 pairを使わないことが短い実装をするの…