ねこ鍋。良問だという話を聞いたので考えてみたらごり押し解を思いついたので実装した。 (cuteのmax)-(cuteのmin)で二分探索することを考える。そうすると、O(N)個の区間でナップサックをして、取れる重さの値をオスメスともに列挙できればよいことがわかる…

本番で解けなかった問題。区間DP。解説だと「区間を木にできるかだと4乗になって、区間を森にできるかどうかを考えると3乗に落ちる」と言われていましたが、「区間を木にできるかどうか」だけで3乗にできます。まず、DP[区間][一番最後の子x]: 区間の左端を…

700を埋め始めました。昨日今日でつぶした4問を載せます。全体的に(というか全部)筋肉。 AOJ 1314 Matrix Calculator ひたすら物量構文解析。行列積の結果が正方行列にしかならないクソバグを埋め込んだのに1ケースしか落ちず苦労した。テストケースが見える…

問題概要 凸多角形の辺上を速度xで、内部を速度yで動ける点が辺上の点から内部の点に移動する時間の最小値を求めよ。(頂点数) 解法 赤い辺が多角形の辺だとすると、真ん中の経路とるのであれば両端のどちらかの経路をとったほうがいいです(距離が適当な一次…

幾何ライブラリをちょっと整備したのでやってみた。解くたびにライブラリが増えるので生産性を感じる。それっぽい点を全部列挙して適当な線分がちゃんと多角形の中にあるかを判定する。O(2^n*n^4)で前処理がO(n^6)なのでTLEはやばそうだけどちゃんとbreakす…

問題 任意の2本を通る直線がちょうどn種類であるような最小の点の個数からなる点集合を出力せよ。 解法 まずk点が一般の位置にあるときk(k-1)/2本の直線が引ける。m個の点が同一直線上にあるとm(m-1)/2-1個直線が減るのでいい感じに直線を減らして目標の数に…

問題概要: N*Mの盤面にK個障害物があって飛車を3つ置いて互いに取り合わないようにする方法を数えろ。 N.M 解法: 適当に包除を考えて自明な場合を抜くと3個の飛車がL字型に並んでるやつを数えればいいことがわかるので頑張ってsegtreeで平面走査しながら数え…

見た目怖いけど実は簡単。各うさぎの偏角ソート順が分かればあとは隣り合う2つの角度を面積が大きくなるように山を登って行くだけなので偏角ソート順を全探索する。隣接する角度の和がpiより大きい場合にちょっと面倒なので微分の零点とかせずに適当に三分探…

新年なので目標です。とざんさんを真似して点数形式です。この形式だと無理そうなことも扱えるからよい。3段階のやつは2つめをクリアできれば良しとします。 センター試験 通ればいいのでこんな感じ。 足を得る 800 840 +6 +2 +2 二次 これも通ればいいので…

やるだけ埋めの最中に楽しみが生えたので書きます。直交座標すると結構面倒なやつが競プロだとarccosとかが使えるために代わりに回転で表現できて複素座標最強になるのを実感したのでコード張ります。結構いい感じになってる気がする。 #include<stdio.h> #include "s</stdio.h>…

コンテスト中のことをいちいち書くのは面倒なのでコードだけ張ります。Day1 Bus 100/100 #include<stdio.h> #include<vector> #include<algorithm> #include<queue> #include<map> using namespace std; vector<int>pat[600000]; typedef pair<int,int>pii; typedef pair<pii,pii>pi4; vector<int>tim[100000]; bool flag[600000];</int></pii,pii></int,int></int></map></queue></algorithm></vector></stdio.h>…

JOI本選に参加してきました。2年連続の10年に一度の大雪が降る中オリセンへ。いろいろあって競技へ。(気力がないので競技のことだけ書きます) 競技開始 1番を見る。簡単。やるだけ。書く。通る(15分くらい) 2番を見る。簡単。やるだけ。書く。なんかバグるけ…

easy: てきとうなぎにgreedyするだけ。 #include<stdio.h> #include<vector> #include<algorithm> #include<map> using namespace std; int maxi[100]; int ps[100]; class AlienAndHamburgers { public: int getNumber(vector<int>typ,vector<int>vec) { fill(maxi,maxi+100,-200000); for(int i=0;i</int></int></map></algorithm></vector></stdio.h>

http://d.hatena.ne.jp/DEGwer/20130101/1357052199 こんな記事を書いたので結果報告です。 IOIに行く ○ たのしかった(小並感) JMO春合宿に行く × 本選落ちました。クソ。 JOI本選金 ××× 本選の時は精神状態がクソクソアンドクソだった。5位(絶望)。パソコン…

§0.はじめにこの記事は、Competitive Programming Advent Calendar Div2013の11日目の記事として書かれたものです。この記事では、列に対して変な操作をして変なクエリがくる系の問題のsegment treeによる解法を説明します。また、「初心者の初心者による初…

文化祭作業(原稿)からの復帰戦。 いつも通りCからあける。 これやるだけでは... やるだけなので適当に書いてpretest通る。 Bをあける。 これもやるだけでは... やるだけなので適当に書いてpretest通る。cinはこわかったのでscanfを使って慣れないchar配列のs…

200回記念。 開始直前までクッキーを増やしている このころはtime machineが欲しいとか言ってた 開始時刻直前になったのでクッキーをやめる 開始 今回もCから開ける。 Cを見るとにぶたんで貪欲が見え見えである。ちょっとChineseと似てる。 にぶたんで貪欲す…

楽しいオフ会でした(吐血) コンテスト会場に到着。六本木ヒルズ、いろいろ入口があって難しい。どこにいればいいのかわからないのでとりあえず一周する。 一周してそれっぽいところに入ったら準急さんに会う。 会場へ 無意識のうちにJOIとICPCで人が分かれて…

ガチ冷え。Easy:適当にやるだけ。231.12点 #include<stdio.h> #include<vector> #include<algorithm> #include<string> using namespace std; typedef pair<char,int>pci; class FoxAndChess { public: string ableToMove(string a,string b) { vector<char>va,vb; for(int i=0;i</char></char,int></string></algorithm></vector></stdio.h>

楽しかったです(区立小中一貫校生並みの感想)

NPCA優勝しました(ドヤ) 最初に問題全部見るが全然わからんする Dが数え上げなので考えたらN^2くらいのDPが見えるが遅いのでちょっと数学すると解ける combinationを足してちょっとやる AC Bが結構解かれている にぶたんっぽい 境界条件とかをうまくどうにか…

ABCともにgreedy要素が少しずつありました。実装軽いし問題面白かったです(小並感)A: 凸関数なので端同士を結んで行ったほうがいい。stackでほげる #include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<stack> using namespace std; typedef long long ll; ty</stack></algorithm></vector></stdio.h>…

IOI行きます(宣言) (日付は0-indexedです)

Luckyとつくけど悪問ではない。問題をどう見てもsegment treeに見える。 「区間にk>=0を足す」「区間の定数cの数を数える」というクエリが必要で、これは「区間の最大値」と「区間の最大値の個数」を持っておけばよい。 しかしこの場合、求めたいものcが最大…

最短路長を送る問題。すごく面白かったので思考過程とか書いておきます。まず、そのまま最短路長を送っても求めるもの1つにつき10Bitsが必要で36*1000*10=360000Bitsくらいかかってしまいまともな点が取れないので、最短路長の持つ性質を考える。最短路長は…

実装が嫌いな人のために発想の難易度の割に実装量が異常に少ない(具体的には50行以下)問題を列挙します。発想が問題なので良問がそろってるはずです。あと多少の数学ゲーが多いですがそれは発想が数学っぽい問題が実装が異常に少ない問題に多いのでで仕方な…

コンテストでの更新面倒でさぼってたけど今回のCodeforcesは特に面白かった&特にいい順位がとれたのでかきます。気まぐれ。朝(昼)は12:00くらいにおきたので眠気は全くなくて、万全の態勢で臨むことができたと思っている。 問題を開く。Aを見る。面倒くさそ…

Div1medをひたすら埋めるゲーム昨日と今日やった分を列挙します208 235.27pt書かれている通りに面倒なシミュレーションするだけ。悪問 #include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll nowrand=1; class QueenInterference { pub</algorithm></vector></stdio.h>…

合宿問題でジャッジでACをとった問題でUPするだけの価値のあるもののソースを張っていきます。Fish(この間のせた) #include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; typedef pair<ll,pii>pi3; int main() { int nu</ll,pii></ll,ll></set></algorithm></vector></stdio.h>…

http://d.hatena.ne.jp/JAPLJ/20120214/1329229478 この記事に対抗して書いてみました。去年のJOI春合宿Day 1では3問の問題が出題されました。 このうちJOI flagは合宿で一番簡単な問題で(それでも例年の合宿の簡単な問題よりは難しく、解けなかった)、Build…