tozangezan.hatenablog.com を一つ一つ見て行きましょう。 競プロ TopCoder Algorithm Highest Rating: 2440 (0点) あの当時はTopCoderがここまで落ちぶれるなんて思ってもいませんでした……。もうTopCoderを目標にするのやめます……。 Codeforces Highest Rat…

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

これはこれの2日目の記事です。今回は、作問時についついやってしまいがちだが、ちょっとした改善によって問題の質をあげることができるような状況をむやみやたらと並べます。コンテストを開こうとしている人とかは確認してみてください。これらを逆に利用し…

"Wolf": that is one word. Thank you. (tozangezan) いろんなコンテスト*1へのリベンジを果たしたかったので果たしました。コンテスト以外： さすがにコンテスト多過ぎでそんなに簡単には国内オンサイトコンテストに対して特殊な感情が生えなくなった。 JOI…

選手時代の参加記はここですスクリーンキャストをしようと思ったので、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>…

13位でなんとか通過しました。基本的にちょっと残すか20000000くらい取る、安いのは捨てる、最後は回収する、固まったら仕方なく取りにいく、 さっさとコードを書いてぶん回す。初心者からいくらふんだくって後半コンテストをいかに妨害するかみたいなコンテ…

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

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

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

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

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

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

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

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

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

参加しました。また5位でした。解法(ドラッグすると見えます) A: やるだけ B: やるだけ C: やるだけ D: やるだけ E: やるだけ F: やるだけG: やるだけH: やるだけ I: やるだけ J: やるだけK: やるだけ L: やるだけM: やるだけ N: やるだけ O: 解決不能 P: 解…

コンテスト中のメモをアップロードします。 以下は1,3,5ページ目です。 以下は2,4,6ページ目です。 250: 累積和をとって個数で割り切れるかどうか 簡単なのでメモは問題概要を把握するために書いた3ページ目の三角形だけです。 // I like wolves!! #include <vector></vector>…

たまに見る二分探索トラップ。 嘘解法ごめんなさい……。 #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からは離れていたのですが、気が向いたので解きました。探索して盤面をつくり、後はたどるだけで頑張ればよいです。何でこれで探索パートが一瞬で実行できるのかはよくわかっていません。 座標を上手く持つ方法が強いて言えば難しいくらい？ #inclu…