AOJ

AOJ 1256: Crossing Prisms

AOJ

頑張る。 全面と側面で同じ形であることを知らなくて無駄にコードを書きすぎた。 #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>…

AOJ 2686: Unfair Game

AOJ

幼稚園児でも解けるような問題だった。具体的には、 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>…

AOJ 1360: Bringing Order to Disorder

AOJ

上手いこと探索。 半分全列挙を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 2688: Card Game Strategy

AOJ

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>…

AOJ 1239: Viva Confetti

AOJ

待ち受ける大きな罠 (誤差)に気を取られていると足元(添え字)がおろそかになるんじゃ。 #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本選 追加分

AOJ

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>…

AOJ 0607: Bubble Sort

AOJ

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

AOJ 1184: 一般化ポーカー

AOJ

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>…

AOJ 2450: Do use segment tree

AOJ

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

AOJ 2448: Area Folding

AOJ

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

AOJ 2453: Presantation

AOJ

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

AOJ 2561: Revenge of Minimum Cost Flow

AOJ

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

AOJ 1334: Cubic Colonies

AOJ

辺と辺の間を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>…

AOJ 2347: Sunny Graph

AOJ

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

AOJ 1170: 古い記憶

AOJ

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

AOJ 2016: プールの監視員

AOJ

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 2597: Color the Map Extreme

AOJ

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

AOJ 2324: Full Text Search

AOJ

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

AOJ 2316: 人魚の魔女

AOJ

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

AOJ 1139: Earth Observation with a Mobile Robot Team

AOJ

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

AOJ 2627: Multi Path Story

AOJ

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

AOJ 1323: Encycling Circles

AOJ

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

AOJ 2226: Psychic Accelerator

AOJ

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

AOJ 2598: Website Tour

AOJ

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

AOJ 2625: Spotlight Movement

AOJ

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

Revenge of JOI2011 予選

AOJ

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

AOJ 1352: Cornering at Poles

AOJ

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

AOJ 2416: XOR Cloister

AOJ

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

AOJ 1293: Common Polynomial

AOJ

構文解析+多項式ユークリッドの互除法。美しすぎるソースコード。 #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>…

AOJ 2346: Runaway Domino

AOJ

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

AOJ 2623: Optimal alpha beta pruning

AOJ

ここ数年のJAGの問題で最もひどいやつ。 問題の概念を理解するのが難しいだけ。説明なしにこんなこと書くのはどうかしてると思う。(本番では問題文が別の問題にすり替わっていてもっと酷かった) #include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int>g[21</int></vector></algorithm></stdio.h>…

AOJ 2379: Bicube

AOJ

sigma425のソースコードが綺麗。 僕のはマジックナンバーでごり押し。 #include<stdio.h> #include<vector> #include<algorithm> using namespace std; char str[60][60]; int h[]={2,3,3,3,3,3,3,3,3,3,3}; int w[]={5,4,4,4,4,4,4,4,4,4,4}; char tkz[11][6][6]={ { "DLU..", "..FRB" }</algorithm></vector></stdio.h>…

AOJ 2427: hosonagaitokoro

AOJ

ほそながかった...通過の順番をそれぞれ決めて後は到着時刻を合わせるようにずらすのを収束するまでやる。収束しなかったらそれは無理配置。 この問題は問題文を何度も読んだことがあるけど、読むたびに誤読している。 #include<stdio.h> #include<algorithm> using namespace st</algorithm></stdio.h>…

AOJ 2445: MinimumCostPath

AOJ

これは面白い。 向かいたい方向と逆に回らないといけない、すなわち遠回りを強要するブロック配置は、スタート付近とゴール付近にしかないことが容易に(ここが本質なんだけども)分かります。ということで赤い場所(50*50もない)は真面目にDPをして、白い場所…

AOJ 2257: Sakura Poetry

AOJ

Aho-Corasick + DP + メモリの定数倍 kuso.... #include<stdio.h> #include<map> #include<algorithm> #include<string> #include<vector> #include<queue> using namespace std; long long mod=1000000007; char in[30]; string table[600]; vector<int>g[600]; struct wolf{ int chi[26]; int mark; int par; int</int></queue></vector></string></algorithm></map></stdio.h>…

AOJ 2571: Floating Islands

AOJ

マッチングの最小化をする。 想定解法では変なことをしてO(N^2)であるが、見るからにMonge DPのDivide and Conquerテクなので、終了。 距離の和の計算で嵌った。 (そういえばDPの式ですが、dp[i][j]: i個目の余った点(サイズ1以上)でj個覆ったときの最小コス…

AOJ 2563: The J-th Number

AOJ

相当いろんな解法があるらしい。考えられる一番直感的な方法で解いた。動的確保の二種の和のsegtreeにpairをぶちこんでソートして後半のクエリで二分探索。動的確保で何個ノードが必要になるのかがよくわからない。計算量(特にソート部分)もよくわからない。…

AOJ 2540: Ancient Commemorative Monolith

AOJ

iとtを間違えてハマった。典型的な防ぎようのないバグ #include<stdio.h> #include<algorithm> #include<string> using namespace std; typedef unsigned long long wolf; wolf mod=1000000007; char gly[26][20][20]; wolf Hash[26]; wolf revHash[26]; int gh[26]; int gw[26]; char in</string></algorithm></stdio.h>…

AOJ 2250: Operator

AOJ

たまに見る二分探索トラップ。 嘘解法ごめんなさい……。 #include<stdio.h> #include<algorithm> using namespace std; int c[1100]; int d[1100]; int e[1100]; int fin[1100]; int next[1100]; int a,b; int can(int M){ for(int i=0;i</algorithm></stdio.h>

AOJ 1303: Hobby on Rails

AOJ

長い間AOJからは離れていたのですが、気が向いたので解きました。探索して盤面をつくり、後はたどるだけで頑張ればよいです。何でこれで探索パートが一瞬で実行できるのかはよくわかっていません。 座標を上手く持つ方法が強いて言えば難しいくらい? #inclu…

AOJ 2615: A + B

AOJ

Bのうち最上位にある1の位置をat(0-origin)とすると 「atの場所は0」「at未満のところを好き放題いじる」という値はBより小さく、この値をCとすると A+Cは「(Aのat以上のbitの1の個数)+at」個の1がある。 これより大きくすることができることもある。ただし…

AOJ 1353: Sweet War

AOJ

dp[i][j][k]: i番目のお菓子でkさんが始めてから先手の人がj得て終わるためには(先手の人のエネルギー)-(後手の人のエネルギー)が何以上/以下であればよいか見てのとおり遷移が複雑です。次の2通りの遷移があります。 i番目をkさんは選ぶ。相手のdpテーブル…

AOJ 2377: ThreeRooks

AOJ

包除原理で数える。 answer = (3つおく全ての方法の数)-(2個同じ線上にある方法の数)+(3つがL字に置かれる方法の数)+(3つが同じ線上にある方法の数)*2あとはNオーバーフローに気をつけましょう。 #include<stdio.h> #include<algorithm> #include<set> #include<vector> using namespace std; </vector></set></algorithm></stdio.h>…

AOJ 2313: Box Witch

AOJ

面倒そう面倒そうと言って毎回逃げていたのでそろそろ仕方なく埋めることにしました。 フローの辺たちを上手くDFSでいじるだけ。練習にはなる。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int D_MAX_V=1100; const int D_v_size=1100</queue></vector></algorithm></stdio.h>…

Solved Ranking 1位

問題大量追加とAOJ-ICPCの整備された環境のおかげでここまでこれました。去年のこの季節に国内予選に落ちてから夏をTopCoderのDiv1Hardに全力を費やし、しばらくたってほとぼりが冷めたころにアジア地区予選があって悲しみを掘り返された勢いでひたすらAOJを…

AOJ 1355: L∞ Jumps

AOJ

ir5さんが解説をslideshareに上げている。本質は使う移動と移動するときのコストの基準点(1になるところ)の対応がGreedyというか両方同じ順であるということで、それが分かっていれば方向全探索O(N^3)、始点O(N)、内部でGreedyがO(N)で解けるという感じ。 4…

AOJ 2633: Cellular Automaton

AOJ

解説の記憶が薄れる前に解いておこうということで。*1・2w+1ビットを一つの頂点として、右に0か1を付け足したときに0,1の総数がどうなるかを計算して辺をはる。辺のコスト(1を付け足すと1がひとつ供給される)と頂点のコスト(オートマトンが1を吐くと1がひと…

AOJ 2183: Crystal Jails

AOJ

存在がクソ解決不能不備問(出題ミス)。どの枝刈りが有効なのかまったくわからず思いついた順に枝刈りを足していくのでこういうのはめちゃくちゃ長くてややこしいコードになる。 #include<stdio.h> #include<algorithm> #include<set> #include<vector> #include<queue> using namespace std; char in[</queue></vector></set></algorithm></stdio.h>…

AOJ 2675: Dungeon of Cards

AOJ

RUPC2015のセットの中で唯一頭を使う問題。 何か見た目がフローっぽかったり変なGreedyを併用するbitDPのようにも思えるが、どれもなんかしっくりこない。ここで3^N個の状態を持つことにして、dp[i][j]を下図のような状況での最小コストとするとすごくすっき…

AOJ 2339: 問題文担当者は働かない!

AOJ

解法にいたった経緯を時系列順に並べる。 小さいケースを確かめてみる。N=2、N=3、N=4…。 N=4、試すことすら困難。諦めざるを得ない。 ちょっとグラフの形を変える グラフが星だとxorで分かるのか。心底どうでもいい。は? なにこれ n時間RucKyGAMESをしなが…