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日目の記事です。 内容は決まってません。

ACM-ICPC アジアつくば大会 2015

にチーム「Sleep 18000」として参加していました. 以下個人視点からの参加記です.0日目(11/27) 学科の友人の家で酒パーティーする.楽しかった.hogloidは泊まってたけど自分は荷物も用意してないし流石に帰った(駅までの道で迷ってしまい焦った).使わないであ…

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 本選(コンテスト)

非コンテスト編は一個前です. A~E:解く. F:見た時に去年の国内予選のサイコロを思い出した.とりあえず変数を置いて式を書くと全部の辺を使う個数が確定したので,ちゃんと0以上になってるか,連結かどうかなどを見ればOK.出したらWAったのでGを見る. G:subtree…

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)与え…

Pathological Paths (AOJ1251)

死んで(直球) 英語10 エスパー力100 頭0 ライブラリ0 実装1 マジでふざけんなよ・・・ 問題文を正しく解釈してください、という問題なので,問題文をちゃんとしたものに変換したものは答えそのものなので書かないことにします. ホンマ死ね(ド直球) ところでAO…

エレベーターホール・ナンバー (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を返して…

敵の敵は味方 (AOJ2403)

極大独立集合列挙.(N 敵の敵は味方 の公式解説スライドは普通に嘘が書いてある("実は極大独立集合を列挙していることに相当"が普通に大嘘 例えば0-1-2 で2のみselectedみたいなのが出てくる)のでこのスライドは無視推奨.次数が小さい順に見ていく(点を選んで…

Cruel Bingo (AOJ2231)

問題:N*Nのビンゴ(ななめあり(対角線2つ))の盤面のうち,N*(N-1)個開いてるのにビンゴができてないCruelな盤面は何個あるか,ただし開いてることが確定してるマスがK個与えられる.N

CF 327

また18:00~のセット なんとなく体調よくなかったのでCすぐ解けたら出ようかなあとか思って開始 Cを読む.読めないのでDを読む.これ自明じゃない?もしかして150^4じゃ落ちるのかなあ・・・ 怖かったのでCが解けるの確信してからDをやろうと思ってCを読む.読む…

KUPC2015

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

CF 323

CF

おもしろかった A:なるほどね B:乗算じゃない累乗系 C:gcdごとにがんばる D:ord_p(nCk)はp進法表記した時のくりあがりの数に等しい(すごくない?)あとは桁DP あとp進表記にするくらいならBigIntegerいらないですね E:bit列に値が定まっていてandした所に結果…

SRM669

writerでした。 解説 div2 easy: 概要:アイドルがライブをしますmapとかを使いましょうmed: 概要:あみまみがゲームをします実はどうくっつけても同じ結果になります 例えばa,b,cとすると a*b + (a+b)*c とかになって,一般に実は異なる二つのすべての積になり…

TTPC2015 解答

とりあえずP以外解けたので(自分の解答なので想定かどうかは知らない)A:やるだけ B:貪欲 C:実装 D:実装 E:特殊マスが関係ないのに右に2つ伸ばす みたいなのは意味が無い(左右に1ずつのばす とかは意味がある) ので2^K * 4^2 全部試せばOK F:0と9以外では揃わ…

TTPC2015 参加記

11:00 頑張って起きる 12:20 六本木に着く 12:30 迷う,森タワー消滅 12:50 ついた 13:00 contestantが遅刻しすぎて延長 13:15 開始 流石にコンテスト中の順を追うのは面倒なので問題番号順で A:やるだけ B:やるだけ C:めんどいやるだけ D:めんどいやるだけ E…

JAG夏合宿2015 参加記

day1 大学の理学部情報学科のガイダンスがあったので行く,理ロシが多かった.まあまあウェイっぽい人もいた.でも地下の部屋は安心感のあるオタクっぽかった.同期や上の人(なぜかtozanも来ていた)と交流した後Sleepの3人とhogloidで直接オリセンに行く.途中で…

Rings (AOJ2562)

クソコード博覧会. 3次元はだいたい球とかで線分とかとの話になって二次式を解くみたいなのになりがちだが、これはまあまあおもしろかった(設定が簡潔なのもよい)とりあえずきれいに回転させたあとz=0平面との交わりを出して円の内外にわかれてるか判定.交わ…

Minimum Spanning Tree (AOJ2559)

典型良問.こういう分割しそうなやつはとりあえずまず一直線の区間で考えるのが吉.そのあとマージの方法を考えればいい(といってもだいたいいわゆるマージテクが効くと思うけど) dfsがstack overflowして悲しかった(事前にbfsして順番決めるだけで回避できる…

影の魔女 (AOJ2315)

nがk個・・・なんか正規分布に近づくとか・・・みたいにに騙されてはいけない(確信). 冷静に式に落とすと簡単. でかいところではN-ボナッチみたいな遷移式(行列)になる(ので直近N個を縦ベクトルで見る) 小さいところははねかえるので線形代数です. #include <bits/stdc++.h></bits/stdc++.h>…

Sports Days 2.0 (AOJ2432)

典型良問. 累乗系の本質は結合法則.ただの乗算だけでなく,a->bへi回移動での(max,min)長さ とかは典型. #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</bits/stdc++.h>…

Speedrun (AOJ2591)

公式解説見ればOK こういう系結構出るから気をつけないとね セーブしうる所を全部持って(実装上Nも入れとくと楽)lower_boundで毎回探して30個くらい回せばOK.実装苦手なのでこういうのですら詰まるんだよなあ・・・ #include <bits/stdc++.h> #define rep(i,n) for(int i=0;i</bits/stdc++.h>…

Trip to Kyoto (AOJ 2618)

適当に書いてダメだったら考えようと思って書いた奴が通ってしまった(まあ大丈夫そうではあったけど) 公式解説がないのでだれか教えて 解法:とりあえず道を無視すると45度回転して中心(座標幅の真ん中)がうれしい.道があってもだいたいそこら辺だろ(ヘラヘラ…

あなたはstackをひとつ持っている

探索して、物を拾ったり取り出したりしてなんらかの対応をつけます きちんと対応付けできるか?とか対応付けの個数の最大値は?みたいな問題があります 典型的な例が Stack Maze (AOJ2538)です この場合探索する場所がDAGなので、区間DPが出来ます。何を持つか…

Hashigo Sama (AOJ2542)

読解3,発想1,ライブラリ0,実装3,やる気4 そんなに難読ではないんだけど,1200+の特性上まず読もうとしてめんどくなってCruel Bingoとかに逃げる とかのパターンから逃げるのが難しい ちゃんと読むと解法は一瞬で生える(多分この部分だけだと300点位じゃないか…

Sweet War (AOJ1353)

A-Bにしかよらないのはまあわかる.A-Bは広い範囲の値を取るので,美味しみの方でメモりたくなる.dp[i][j]="i個目以降で(先手が)おいしみjを得るのに必要なエネルギー格差"を持って更新すればいいです.初め逆シミュレーションみたいなのをして頑張って更新をO(…

天下一2015 qualA

13位でした。 Bから開く,あっ(察し) Cを見る どうせ二部マッチング→ちょうどうまくいく二つ以外(奇数サイクルの)swapする意味が無い(そいつらを全部変えればOK)ので二部マッチングするだけ.HとWを間違えて1WAのあとAC. Aを見る.普通に1WAした後展開図をググ…

戻すDP

物体がN個あって何らかのDPをする時、dp[i+1]からdp[i]を復元できる時、復元することを戻すDPという. いや、dp[i]からdp[i+1]を計算したんだからそんなことしても意味ないやろ、と思うかもしれないが、ちゃんと意味があって、"物体を使う順番が関係ない"場合…

TCO2015_2C Japan onsite

に行きました.楽しかった.13:00 当然のように駅から迷う,それどころか建物内でも迷った,と思っていたらそもそも建物が違うとかいう案件(メールに嘘(歌舞伎座タワー本社ではなく松竹スクエアと書いてあった(住所もそっちだった))が書いてあったんだよなあ).そ…

How to Create a Good Game (AOJ2230)

これは1100だと思う 知識5+,頭3,実装力1,ライブラリ力1問題: 正の重み付きDAGで,さらに,任意のiに対し0->i->N-1となるpathがあるものが与えられる.0からN-1への最長距離を変えないように辺の重みを0位上の整数増やす.どれだけ増やせるか.N

Common Palindromes (AOJ2292)

知識4 頭0 実装1 気合1 英語0 700点くらい問題 文字列s,t(長さ50000まで)が与えられる.s[i..j]=t[k...l]かつこれが回文 となるi,j,k,lの組は何通りか.

Kth Sentence (AOJ2341)

500点問題: lowercaseからなる文字列(長さ200まで)がN(複数回使っても良いし,一回も使わなくても良い)できる長さM(

落書きの魔女 (AOJ2314)

苦行だった・・・問題: H*Wのマス目がある.それぞれを#か.で塗る いくつかは既にどれで塗るか決まっている.残りのマスの塗り方のうちもっとも#が多いもののマス目全体の#の数を答えよ.正しいかの条件を満たして塗る必要がある".は連結(4-neighborsで)しない"…

Dungeon Creation (AOJ2393)

H*Wのグリッドで各マスは白か黒で塗られている.H*(W-1)+(H-1)*W個の壁それぞれを立てるか立てないか決めて,全体が連結でサイクルが無いようにする方法は何通りか.迷路→全域木→行列木定理 O(N^3) (N=H*W=7500) だし無理 W=15だしbitDP?→上から埋めてくと実は…

CF #310

CF

はじまったの20分くらい気づかなくて不参加した. 終わった後出ればよかったなあとか思ったけどやってみたらWAを生やしまくったので出なくてよかった(結果論)A.問題を勘違いしていた.そりゃ4に入れる時5に入ってたらダメだよな・・・ B.区間と点の(完全)マッ…

ICPCdomestic2015 参加記

sleep 18000(@wafrelka @wo_M @sigma425)の3人で出ていました. 問題 順位表東大内3位,全体4位で通過しました.やったぜ.開始前 スクフェスをしたりリハーサル pic.twitter.com/6RDGDZiYfS— SRM510 (@sigma425) 2015, 6月 26 かわいい画像を送ったり@mofmoffox…

フロー押し戻し系

実装を何通りか試してみた,AOJ2313 ハコの魔女 にsubmitして確かめてますa.隣接行列で持つ(int G) N b.vector Gを持つ Nがもっとでかいとaの方法は無理.しかしこれにはまあわかりやすい欠陥があって,eraseが遅いです.(sortしててもダメで,なぜかというと消し…