Programming

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 曲がれ…

Rotate and Rewrite (AOJ1191)

クッッッッッッソ良問だと思う 問題:文字列に対し,rotate(abcd->dabc)とrewrite(与えられたルール(文字列と文字のペア)に対し,今の文字列のsubstringとしてその文字列が現れたらそれをその文字に置き換える)が好きな順で何回も行える.文字列が二つ(A,B)与え…

エレベーターホール・ナンバー (AOJ2587)

問題:N(頭2,実装4,ライブラリ4みたいな解法と頭4実装2ライブラリ0みたいな解法がある.前者の解法は,出来る数字を受理するNFAをつくる→power constructionでDFAにする→topological順序でDPする というだけNFA,DFA,minimizeDFA,NFAtoDFAあたりは持ってなかった…

Sun and Moon (AOJ2455)

問題文が読めない人のために問題文を書くと, N( Σ(グループAに属している人)o[i]*p[i]*x^(o[i]-1) = Σ(グループBに属している人) 左同 かつ Σ(グループAに属している人)p[i]*x^o[i] = Σ(グループBに属している人) 左同 をみたすような最小の正整数xを返して…

KUPC2015

東京オンサイト参加しました. 行く途中で会場位置が変わって焦る.変なルートを通り(鷺沼→永田町→(徒歩)→赤坂見附→銀座) まあ結局駅出てから迷った. sugimさんと席が隣になった,勝つぞ~(ちなみにrngさんが前だった)5時間12問. 13:00 20分開始が遅れる 13:20 …

NYC2015

New Year Contest2015 解けそうな奴を解き直した. A:やるだけ B:やるだけ C☆:直前と異なるものを挿入→初め以外割りと何でもできる D:対称位置にジャンプ→xと-xからdijkstra E: "次数がd1~dnの木 (Σdi=2*(n-1),di>0) の総数は(n-2)!/Π(di-1)! だから終わり" …

天下一2014 QualA

全然駄目でした(A,Cの2完) A:ついこないだTo_string関数を自分で書いた(ostringstreamを使う)ので覚えていた、多言語だとより簡単?B:問題文読解が激ムズ、ここまで悪意のある問題文は普通書けない.明らかにこのセットの中で一番むずい.かぶりん死ね(かぶりん…

CF #260

つらい・・・ミス: A:ループ終える地点をミスる B:根付き木のdfsだからメモ化してなかったけど辺が重複していた C:純粋に解くのが遅いメモ: A:適当に手元でテスト B: Trie木の実装としては、通し番号を付けるのは同じだが struct trieの中でstruct nodeの配…