ARC055

writerでした。 AtCoDeerくんというシカが主人公です。公式キャラに定着させたい・・・AtCoderのマスコットキャラクターのAtCoDeerくんというのを思いついたので自由に使っていいですよ(ロゴの横にいるやつをシカということにしてこいつらをマスコットキャラ…

Rabbit Jumping (AOJ2384)

アホでしょ・・・ 頭0,ライブラリ0,実装1145141919くらいといってもうまいこと実装方針を立てられれば綺麗に書けるのかなあ・・・解法:コードを書きます これでほとんどバグ起こさなかったのすごいと思う 誰かいい実装を教えて下さい(まあ向きの2^k試すのは…

締まっていこう (AOJ1164)

たわみを無くすまで引っ張る・・・はせずに解きました. 解法はrngさんがこどふぉで記事に書いているとおりです. しかし実装の細かい部分が結構たいへんだった. まず,始点,終点をどう扱うか.ピンの点と同様に扱おうとすると,上をとおるか下をとおるかみたいな…

Presentation (AOJ2453)

問題: Presentation | Aizu Online Judge考えれば解ける系の綺麗な問題. でも1100はない気がするなあ(900くらい?) 一度ある木をコピーすると,その木を組み合わせたようなものしか出来ない.その木Xを使ってできるかの判定は根から順にdfsをすればできる(実際…

CF345

19位で赤に戻った はじめてCFとTC両方赤になった やったぜ。Copenした C:大小関係(のうち最も近いものだけ)でDAGを作り,最短経路を求めればいい.先にunionfindしたけど,よく考えるとSCCすればよかった. A:同じ点があることに注意して数える B:片方どこまで行…

range tree

とりあえず2次元で,クエリが点追加と矩形カウントできるデータ構造の話をします.まずある点(a,b)から左下にある点の数を数えられれば矩形カウントが出来ることに注意. 座標幅は縦横ともにL,クエリN個とします(当然点の数もN以下)蟻本にも載ってる,マージソー…

STLメモ

間違ってても知りません string::substr(i,n) i,nはsize_t(unsigned) i>Nだと配列外アクセスだが,nを無駄に大きくとってもちゃんと最後までに設定してくれる nを指定しない場合も最後までになる rotate()

RUPC2016

RUPC2015だと思ってました.day1 家で出る.Eまでやった後Fが多方向木DPっぽいなあと思った後,Gに手を付けてしまいコンテストが終了した. A:やる B:前から1に→後ろから0に C:やる(はじめ制約読んでなくて不可能ってなってた) D:ひとつのscannerは50*ceil(50/3)…

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

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を…