Programming

Company Organization (AOJ1332)

問題: 1~Nの番号がついた集合がある.集合間の制約が順にM個来るので,どこで最初に矛盾するか答えてください. 制約は5種類で, 1:A⊆B 2:A=B 3:A≠B 4:A∩B=∅ 5:A∩B≠∅ タイプとAとBの番号が制約として与えられる. N≤100,M≤10000 頭1,実装1,ライブラリ1 簡…

SRM683

わりと面白かった反省点: easyでオーバーフローさせた medでauto&とすべきところをautoにしていた hardで配列外アクセスを起こした(これはコンテスト後) Easy: N個の正整数が円状に並んでいる.隣り合ったものに+1,-1を足すことができる.最小で何回操作すれば…

ディスコン2016 本選

正式名称は DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選. DDPCっていうとTTPCみたいな感じがあってなんだっけそれってなるのでわかりづらいのでディスコンって呼んでました. ほんまに大反省. 前日:よすぽと一緒に某家にお泊…

TCO2012 Round2C d1m ThreePoints

ネタバレ 多分rng問題のほうにも軽く書くと思うけど別立てで.問題:平面上の点(x[i],y[i])がN(<=300000)個与えられる.次を満たすa,b,cの組の個数を求めよ:x[a]

第二回ドワンゴからの挑戦状 本選

出てました。C,Dに手が出ず終了。コンテスト中 A:流石にやるだけだと思ったんだけど案外みんな引っかかったらしい.微妙にsemiexpさんに負けた. B:やるだけ.普通にsem(ry C:個人的にはかなり難しかった.O(N^2)は思いついたので(各区間に対しどの高さの点が入…

第二回ドワンゴからの挑戦状 予選

出ました.7位でした.はまらずにEの部分点まで解けて予選通過できてよかった(あとで順位表見たらちょっとでもはまってたらダメそうだった)A:全部25の倍数.コンパイルせずに出したけどFAじゃなかった,かなC B:左右のどっちかの数字以外にする意味はなくて,どっ…

rng問題

↓URL rng問題 - Google スプレッドシート埋めてます 面白かった問題を順次追加していきます ネタバレしてるので注意です ColorfulCards (SRM495 d1e/d2m) できるだけaなことをする+できるだけaでないことをする(貪欲) をして同じ結果なら1通りCarrotJumping …

Dominator Treeの記事で飛ばしたとこ

ここまで読むなんて偉い、けどここを読むくらいなら元論文を読んだほうがいいと思うよ Them1がないのは元論文ではdominator treeの性質のとこがthem1になってたからです.Lem1: v,w∈Gでv≦wなら,vからwへの任意のpathはTにおけるvとwの共通祖先のうち少なくと…

Dominator Tree

2017/01/04追記 非連結だとバグります☆ はじめに はい、というわけで今日はね、今流行りのDominator Treeについてね、書いていきたいと思います。 Competitive Programming (その2) Advent Calendar 2015 - Adventarの12/25の記事の予定です。参考論文は "…

CodeFestival2015沖縄ツアー

12/18(0日目) SRMで激冷えする つらかった12/19(1日目) 空港に行く(ギリギリ) 全然準備してなくて結局印鑑も名札も忘れてしまった.沖縄へ飛びホテルへ着く.まわりを適当に散策(海で石切りしたりしていた)する.スーパーに遊びに行く.ルートビアをjapljさんに…

Social Monsters (AOJ2605)

典型円環系. 頭0,実装3くらい dfsで円環を順に見ていけばいい.線分もあるので,線分のnot端からまちがえて始めちゃわないように注意. なんだかんだ言ってこういうのに30分かけるのはもったいないよなあ でもかかるんじゃ. #include <bits/stdc++.h> #define rep(i,n) for(int</bits/stdc++.h>…

Mobile Network (AOJ2328)

続く550点地帯この問題は問題文を読んでもエスパーしないと解けないので,問題を説明すると,capが一変数(x)多項式の最大流(正確に言うと,多項式P(x)であって,xが十分大きい時にそれを代入したグラフでの(実数)フローとP(x)にxを代入した値が一致するもの)を求…

Water Tank (AOJ2180)

でんじろう先生じゃない方のWater Tank.こっちは打って変わってクソ簡単.なんで550なの・・・ にぶたんするだけ.しいて言うなら一周では足りないことに注意(二周して減ってるかどうかチェック) まあサンプルで分かるよね #include <bits/stdc++.h> #define rep(i,n) for(int</bits/stdc++.h>…

まるかいて (AOJ2429)

どうみてもフロー コストを行にわけて考えるとよい(各行でひとつしか選ばれないので) #include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #de</bits/stdc++.h>…

MinimumCostPath (AOJ2445)

なんとなくそうっぽいなあ というのはすぐわかるんだけど, ちゃんとそれでいいかどうかというのがなかなか難しかった.基本的に,あんまりでかいと,x+y=200と(N-x)+(N-y)=200とかで線を引いた時に(線a,bとする),a上の点からb上の点に行く時に遠回りをするやつ…

Tatami (AOJ2163)

枝刈り探索をします.(ちゃんと考察すると1次元DPにできる と解説には書いてあるが,結構難しい気がする) おけない条件を点で考えるんじゃなくてななめで隣り合うところの置き方の問題として捉えるのが楽. 次にどこに置くべきか(候補が一番少ないところにする)…

Name the Crossing (AOJ1134)

ほんとに面白く無いんで読まないでいいです カレンダーを埋める用の記事. 本質はクエリ部分の入力としてそもそも存在しない通りの名前が来ることです. あとはやるだけ(よく見ると通りは200個しかないと書いてあるのでsccすらいらない)これカレンダーとしての…

Earth Observation with a Mobile Robot Team (AOJ1139)

バグらせた.死にたい. まず最短で交わるタイミングだけ求めればいいとかいう嘘を書いてしまったのが問題なんだよなあ(すぐ修正できたけど) あと二次方程式間違えてたのは♨. 微妙に7日に間に合わなかった・・・ あと幾何ではない問題として,人aとbが会えるタ…

何も決まってないです。(path上の最大重みを求めるの一般的なテク)

はじめに この記事はCompetitive Programming Advent Calendar 2015 - Adventarの7日目の記事です。 内容は決まってません。

Water Tank (AOJ1133)

えっと、でんじろう先生の方のWater Tankです. これクソむずいと思う・・・ 実装方針を評価して個人的には700点くらい(もちろん実装強い人は何やっても解けるんだけど,うまい方針がある)とりあえず計算量はどうでもいいのでtごとに毎回計算します. h[i]:左か…

Gravity Point (AOJ2626)

わりとすぐ解法がわかり,実装方針も適切なものを選び,実装もすぐ終わったのにccwを写し間違えてたからデバグに40分かかりました.変えたらそっから変更無しでACしたので実質バグ埋めてないしすごくない?(すごくない,写経ぐらいちゃんとしろ)とりあえずA,B,Xを…

Spotlight Movement (AOJ2625)

こういうライブラリいらないなんちゃって幾何大好きだからもっと出してくれ(例:流れ星に願いを(AOJ2586)) 線分上を等直線運動する二点の最小距離 は二次式の最小化だと思える.やることがほんと少なくてすき. でもこんなの解いても全然強くなる気しねえな・・…

Area of Polygons (AOJ1242)

スライスするだけ・・・と思っていたら結構ミスった スライスするとき,+-epsして点と絶対に被らないようにすれば交点のx座標を列挙した時個数は偶数になる([0,1],[2,3]..みたいになる)し,x+epsとx+1-epsの交点は順に対応することがわかる. #include <bits/stdc++.h> #define</bits/stdc++.h>…

MirrorLabyrinth (AOJ2514)

まあやるだけ・・・ (凸とは限らない)多角形2つのcapでできる多角形?上での最短路 を求めようとするときに,実は元の多角形の頂点しかいらない というのはそんなに自明ではない気がする(いや言われたらわかるんだけど,言われずに思いつくもんだろうか) あとは…

Don't Burst the Balloon (AOJ1342)

円とかで削って残る点があるか→交点すべてをゆるい条件で調べる containCCは細かいことを考えると結構面倒 #include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #def</bits/stdc++.h>…

Time Table (AOJ2603)

今気づいたんだけど,問題名Time Tableなんだね,ずっとTiMe Tableだと思ってた(AOJ-ICPCの表記がそうなってる). 追記:asiさんのコメントの通り,TiMe Tableが正しいようです,AOJ側が間違ってるようだ. さらに追記:square1001さんのコメントの通り,AOJの表記もT…

Ancient Commemorative Monolith (AOJ2540)

やるだけでしょ 流石に900点もなくない?(少なくともASCII Expressionよりは絶対に楽だと思う) 英語4,頭0,ライブラリ0正直細かい制約から,こういうめんどくさいケースはないんだなあ みたいなことを考える時間が面倒なだけ.しかも細かい制約は文章中とかにう…

BIT

毎回こんがらがるのでメモ.自分用なので読んでも意味ないよ.(それどころか悪影響かも) segtreeの右の子を全部消したような奴(左から累積和を取るのに兄弟をふたりとも使うことはないので) 1=1 2=2 3=2+1 4=4 5=4+1 6=4+2 7=4+2+1 8=8 みたいになるので1-inde…

CODE_FESTIVAL 2015 本選(コンテスト以外)

参加したので参加記を書きます.参加記を書くまでが(略) 0日目(11/13) 夜までカタンをやった後寮の友人で一緒にこどふぇに行く人に何時に出ればいいか調べてもらい,クソはやくて絶望する.急いで寝る. 1日目(11/14) 9:00くらいに起きる.↑の人と一緒に会場に行…

Mysterious Maze (AOJ2325)

ちょっと嵌ってしまった迷路があり,はじめ北を向いている.曲がれボタンとすすめボタンがあって好きな順で押せるが,曲がれボタンをi番目におした時右か左に曲がるかは決まっている.曲がれボタンを押し切った時にゴールにたどり着けるか? 迷路1000*1000 曲がれ…