続く550点地帯この問題は問題文を読んでもエスパーしないと解けないので,問題を説明すると,capが一変数(x)多項式の最大流(正確に言うと,多項式P(x)であって,xが十分大きい時にそれを代入したグラフでの(実数)フローとP(x)にxを代入した値が一致するもの)を求…
でんじろう先生じゃない方のWater Tank.こっちは打って変わってクソ簡単.なんで550なの・・・ にぶたんするだけ.しいて言うなら一周では足りないことに注意(二周して減ってるかどうかチェック) まあサンプルで分かるよね #include <bits/stdc++.h> #define rep(i,n) for(int</bits/stdc++.h>…
どうみてもフロー コストを行にわけて考えるとよい(各行でひとつしか選ばれないので) #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>…
なんとなくそうっぽいなあ というのはすぐわかるんだけど, ちゃんとそれでいいかどうかというのがなかなか難しかった.基本的に,あんまりでかいと,x+y=200と(N-x)+(N-y)=200とかで線を引いた時に(線a,bとする),a上の点からb上の点に行く時に遠回りをするやつ…
枝刈り探索をします.(ちゃんと考察すると1次元DPにできる と解説には書いてあるが,結構難しい気がする) おけない条件を点で考えるんじゃなくてななめで隣り合うところの置き方の問題として捉えるのが楽. 次にどこに置くべきか(候補が一番少ないところにする)…
ほんとに面白く無いんで読まないでいいです カレンダーを埋める用の記事. 本質はクエリ部分の入力としてそもそも存在しない通りの名前が来ることです. あとはやるだけ(よく見ると通りは200個しかないと書いてあるのでsccすらいらない)これカレンダーとしての…
バグらせた.死にたい. まず最短で交わるタイミングだけ求めればいいとかいう嘘を書いてしまったのが問題なんだよなあ(すぐ修正できたけど) あと二次方程式間違えてたのは♨. 微妙に7日に間に合わなかった・・・ あと幾何ではない問題として,人aとbが会えるタ…
はじめに この記事はCompetitive Programming Advent Calendar 2015 - Adventarの7日目の記事です。 内容は決まってません。
にチーム「Sleep 18000」として参加していました. 以下個人視点からの参加記です.0日目(11/27) 学科の友人の家で酒パーティーする.楽しかった.hogloidは泊まってたけど自分は荷物も用意してないし流石に帰った(駅までの道で迷ってしまい焦った).使わないであ…
えっと、でんじろう先生の方のWater Tankです. これクソむずいと思う・・・ 実装方針を評価して個人的には700点くらい(もちろん実装強い人は何やっても解けるんだけど,うまい方針がある)とりあえず計算量はどうでもいいのでtごとに毎回計算します. h[i]:左か…
わりとすぐ解法がわかり,実装方針も適切なものを選び,実装もすぐ終わったのにccwを写し間違えてたからデバグに40分かかりました.変えたらそっから変更無しでACしたので実質バグ埋めてないしすごくない?(すごくない,写経ぐらいちゃんとしろ)とりあえずA,B,Xを…
こういうライブラリいらないなんちゃって幾何大好きだからもっと出してくれ(例:流れ星に願いを(AOJ2586)) 線分上を等直線運動する二点の最小距離 は二次式の最小化だと思える.やることがほんと少なくてすき. でもこんなの解いても全然強くなる気しねえな・・…
スライスするだけ・・・と思っていたら結構ミスった スライスするとき,+-epsして点と絶対に被らないようにすれば交点のx座標を列挙した時個数は偶数になる([0,1],[2,3]..みたいになる)し,x+epsとx+1-epsの交点は順に対応することがわかる. #include <bits/stdc++.h> #define</bits/stdc++.h>…
まあやるだけ・・・ (凸とは限らない)多角形2つのcapでできる多角形?上での最短路 を求めようとするときに,実は元の多角形の頂点しかいらない というのはそんなに自明ではない気がする(いや言われたらわかるんだけど,言われずに思いつくもんだろうか) あとは…
円とかで削って残る点があるか→交点すべてをゆるい条件で調べる 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なんだね,ずっとTiMe Tableだと思ってた(AOJ-ICPCの表記がそうなってる). 追記:asiさんのコメントの通り,TiMe Tableが正しいようです,AOJ側が間違ってるようだ. さらに追記:square1001さんのコメントの通り,AOJの表記もT…
やるだけでしょ 流石に900点もなくない?(少なくともASCII Expressionよりは絶対に楽だと思う) 英語4,頭0,ライブラリ0正直細かい制約から,こういうめんどくさいケースはないんだなあ みたいなことを考える時間が面倒なだけ.しかも細かい制約は文章中とかにう…
毎回こんがらがるのでメモ.自分用なので読んでも意味ないよ.(それどころか悪影響かも) segtreeの右の子を全部消したような奴(左から累積和を取るのに兄弟をふたりとも使うことはないので) 1=1 2=2 3=2+1 4=4 5=4+1 6=4+2 7=4+2+1 8=8 みたいになるので1-inde…
非コンテスト編は一個前です. A~E:解く. F:見た時に去年の国内予選のサイコロを思い出した.とりあえず変数を置いて式を書くと全部の辺を使う個数が確定したので,ちゃんと0以上になってるか,連結かどうかなどを見ればOK.出したらWAったのでGを見る. G:subtree…
参加したので参加記を書きます.参加記を書くまでが(略) 0日目(11/13) 夜までカタンをやった後寮の友人で一緒にこどふぇに行く人に何時に出ればいいか調べてもらい,クソはやくて絶望する.急いで寝る. 1日目(11/14) 9:00くらいに起きる.↑の人と一緒に会場に行…
ちょっと嵌ってしまった迷路があり,はじめ北を向いている.曲がれボタンとすすめボタンがあって好きな順で押せるが,曲がれボタンをi番目におした時右か左に曲がるかは決まっている.曲がれボタンを押し切った時にゴールにたどり着けるか? 迷路1000*1000 曲がれ…
クッッッッッッソ良問だと思う 問題:文字列に対し,rotate(abcd->dabc)とrewrite(与えられたルール(文字列と文字のペア)に対し,今の文字列のsubstringとしてその文字列が現れたらそれをその文字に置き換える)が好きな順で何回も行える.文字列が二つ(A,B)与え…
死んで(直球) 英語10 エスパー力100 頭0 ライブラリ0 実装1 マジでふざけんなよ・・・ 問題文を正しく解釈してください、という問題なので,問題文をちゃんとしたものに変換したものは答えそのものなので書かないことにします. ホンマ死ね(ド直球) ところでAO…
問題:N(頭2,実装4,ライブラリ4みたいな解法と頭4実装2ライブラリ0みたいな解法がある.前者の解法は,出来る数字を受理するNFAをつくる→power constructionでDFAにする→topological順序でDPする というだけNFA,DFA,minimizeDFA,NFAtoDFAあたりは持ってなかった…
問題文が読めない人のために問題文を書くと, N( Σ(グループAに属している人)o[i]*p[i]*x^(o[i]-1) = Σ(グループBに属している人) 左同 かつ Σ(グループAに属している人)p[i]*x^o[i] = Σ(グループBに属している人) 左同 をみたすような最小の正整数xを返して…
極大独立集合列挙.(N 敵の敵は味方 の公式解説スライドは普通に嘘が書いてある("実は極大独立集合を列挙していることに相当"が普通に大嘘 例えば0-1-2 で2のみselectedみたいなのが出てくる)のでこのスライドは無視推奨.次数が小さい順に見ていく(点を選んで…
問題:N*Nのビンゴ(ななめあり(対角線2つ))の盤面のうち,N*(N-1)個開いてるのにビンゴができてないCruelな盤面は何個あるか,ただし開いてることが確定してるマスがK個与えられる.N
また18:00～のセット なんとなく体調よくなかったのでCすぐ解けたら出ようかなあとか思って開始 Cを読む.読めないのでDを読む.これ自明じゃない?もしかして150^4じゃ落ちるのかなあ・・・ 怖かったのでCが解けるの確信してからDをやろうと思ってCを読む.読む…
東京オンサイト参加しました. 行く途中で会場位置が変わって焦る.変なルートを通り(鷺沼→永田町→(徒歩)→赤坂見附→銀座) まあ結局駅出てから迷った. sugimさんと席が隣になった,勝つぞ～(ちなみにrngさんが前だった)5時間12問. 13:00 20分開始が遅れる 13:20 …
おもしろかった A:なるほどね B:乗算じゃない累乗系 C:gcdごとにがんばる D:ord_p(nCk)はp進法表記した時のくりあがりの数に等しい(すごくない?)あとは桁DP あとp進表記にするくらいならBigIntegerいらないですね E:bit列に値が定まっていてandした所に結果…
