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