unsolved

uwiさん等を見習ってここにメモります OpenCup FHC 2016r2 SRM SRM705 hard 線形代数 SRM706 hard SRM707 SRM708 SRM709 SRM710 CF goodbye2016 H http://codeforces.com/contest/750/problemshttp://codeforces.com/contest/757/problem/G AtCoder AGC ARC6…

メモ

知らなかったできることのメモとか1e18+3(codeではll 1LLe18+3)は素数 inv(1e9+7) mod(1 DAGにpathを何個書けば頂点が覆えるか->bipartite matching 和がnになるような1以上の整数達がいる時、種類は√2nくらい (よく考えたら自明だった) 負辺min_cost_flowは…

yukicoder ☆5,6

何故か埋めています。解法メモなのでネタバレ注意。 ☆5 42: 63: 93: 変なことをすると下から挿入できるが、普通に包除 114: 137: 特異問題です。これはむずい 1,x,x^2,..なら順番に倍数だから、modでピッタシになるようにdpするっていうのが出来たわけだが、…

UTPC2011

D:探索ゲーでpair<pair<int,int>,pair<int,int>>とかやるのつらいので、tupleを使う.勝手に辞書順が入ってるのでsetに入れられる using State = tuple<int,int,int,int>; queue<State> que; que.push({1,2,3,4}); int a,b,c,d; tie(a,b,c,d) = que.front(); cout<</state></int,int,int,int></int,int></pair<int,int>

SRM710

難しすぎる. 0完で-100くらいくらって黄色になった.easy: AとBは逆操作.なのである標準形みたいなのを設定してそこに持っていけばいい.標準形としてはぜんぶおなじとこに集まってるのとかを選べば良くて、これに持っていくにはAを選びまくれば良い.操作が二…

CF395

Eの賢い解法を見つけたのでメモのついでに A: 色が異なるu-vを見つけたらuかvを選ばねばいけないB: x1%2,y1%2で類別すると同じのは接さないC: N=1,Mを除いておくと、総和の式からxとdの一次式が出てくる.同様に二乗和の式による制限によって高々二通りにまで…

SRM707

起きたら始まってたんですけど、結果から言うと出なくてよかった・・・ easyとmedが思考パートが無な上にかなりひどかった.しかもChalゲーだったのでかなり自分にはきつそう.easy: 本当にただやるだけ、FAのコードも見たけど方針が違うとかではなく単純にた…

AGC009

DEGwerは天才。 日露交流コンテストみたいなのが事前にあったのでネタバレを抑えるのが大変だったA:後ろは押す場所が一意に決まるので後ろから決めていく貪欲.B:xが誰に勝ったか、というのはわかるので、その部分をどういう順で戦わせるか考えると、相手のト…

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

コンテストはひどい結果になりました。 懇親会ではなんとミスケンさんが来ていて、ぷよ通で対戦しました。めっちゃ貴重な体験ができて楽しかったです。(はじめ操作が難しかった) ありがとうございました(dwango作のC問題も割ときれいな問題だったので良かっ…

__int128

は僕の環境だと使えないんですけど、(gccのバージョンではなくハードの問題なんですかね)AtCoderでは使えます(使う問題なんてほぼ出ないだろうけど). Ideoneだと使えないです. 演算はだいたい大丈夫だけどcin,coutは自分で書きましょう. 気づいたんですが負…

JOI春

問題一覧 - 情報オリンピック 問題と解説 2012年 日本情報オリンピック春合宿OJ - 2012年 日本情報オリンピック春合宿OJ | AtCoder 2013年 日本情報オリンピック春合宿 1日目 - 2013年 日本情報オリンピック春合宿 1日目 | AtCoder 2014年 日本情報オリンピ…

ICPCつくば2016

が10/15,16にあったんですが、参加記を書いていなかったので書きます。 今年もsleep 18000 (sigma,wafrelka,wo) で参加していました 10/14 消費期限切れの牛乳を持ってないことを確認する 10/15 早起きしたけどライブラリ印刷したりしてたらギリギリの時間に…

AGC006

死んだ。 まためっちゃ面白いセットだった。sugim48すごすぎ。A:流石にやるだけ B:いきなり難しいconstructive. 実験したらrotate(ans+x-2,ans+x,ans+N) が見つかったのでこれを出力した。D考えてるときに真ん中でa

FunctionalEquation (SRM456hard)

おもしろかった.問題:整数1&leq;C&leq;16 と, x[i],y[i]が与えられる. f:Z->Zで,f(2f(x)-x+1)=f(x)+C を満たすという条件のもとでsigma |f(x[i])-y[i]| を最小化せよ. x,yの長さは まずxに2f(x)-x+1を再代入しするとf(x+2C)=f(x)+2Cが得られる. 逆に, f(x+2C…

yukicoder No.284 門松と魔法(2)

発想は良問.実装が大変.問題:数列が与えられる,部分列Bであって,B[i]!=B[i+2] かつ (B[i]<B[i+1]>B[i+2] または B[i]>B[i+1]</b[i+1]>

天下一2016本選

ほんとうにつらい・・・ C,Dをやって,Eでcinを使ってTLEをした後,FをスルーしてAとBに向かってしまい,結局BはN&leq;10までしか解かないコードを,Aは996頂点0辺の1彩色可能なグラフをsubmitして終了してしまった. F,得意系だったのでスルーしてしまったのは本…

JAG2016夏合宿

に参加しました day1 補習に行って、なぜか自分のPC上の仮想環境(VMware)が立ち上がらなくなっていることに気づく。そこでいろいろやってたら遅刻した(ごめんなさい)。sugimさんがいないので自己紹介でsugimを名乗りかける。談話室でボドゲをやる。The Boss…

CF AIM Tech Round 3 (Div. 1) (708)

A:場合分け はじめのaじゃないとこからaじゃないとこまでだけどaaa->aazに注意 B:場合分け 0がない時と1がない時とそれ以外で,それ以外だと0と1の数がわかるので全体と合ってることを確認した後は適切に0001111からずらす(計算して). C:全方向木DP.dp[v]=v以…

TreeDistance (TCO14 Round 3B d1 hard)

問題:N頂点の木Tが与えられます.「辺を一つ除いて,新たに付け加えて木にする」 という操作をK回以下出来るとき何種類の木が出来るでしょう?N,K&leq;50まず, TからK回以下で木Xに出来る⇔TとXの両方に含まれる辺がN-1-K本以上(→は自明,左はいつかのこどふぉEに…

包除

a1,a2,..aNのうち,K個以上を満たす物の数は, 一々計算するのが面倒なので(ちなみに,K=0の時はC(-1,-1)=1だけ生き残る)ちょうどK個は,まあ差をとればいいや.

Mr. Kitayuta vs. Bamboos (CF286 C)

Problem - C - Codeforcesクッソ良問.CFのCに置かれて虐殺が起こった.問題:竹がN本あり,はじめ高さはそれぞれh[i]である. 1日で起こることは,「 (竹を選んで"ハンマーで叩く")をK回以下 → それぞれの竹がa[i]伸びる」 ここで,高さhの竹をハンマーで叩くと,高…

Typical DP Contest (TDPC)

Typical DP Contestとは,りんごさんが作ったDPの問題で典型的すぎて一般的なコンテストに出せないと(りんごさんが)判断した,DPの練習問題を集めたものです が,十分難しい難易度のものもあります.2013/8/31に開催されたんですがようやく全問解いたのでメモ.(…

AGC002

ほんとうに最下位だったA:OK B:OK C:最後の一個が出来る二本があるならできるし,そうでないならできない. D:永続UFかと思ったけど,クエリを同時ににぶたんするのにlog幅回走査する方法がある.知らなかった. E:終了20sec後とかに通った.図形まではすぐに落と…

天下一プログラマーコンテスト2016 予選A

14位だけどqualifiedの中では10位以内っぽいのでギリギリセーフだった.A:fizzbuzz B:できるだけ上に回したほうがいいのでminにあわせる 簡単で綺麗なDPですき. C:文字列同士を見てはじめに異なる文字しか関係ないのでそこで文字の情報にしてaよりbがはやい …

CF359

解きました.virtualでA,B,Dの3完でした.A:ひねりのない簡単なやるだけ. B:すべての部分木に対して重心を一つ求める問題. サイズと重心を持ちながら木DP.根が重心になるならOKで,そうでないなら一番大きい子の重心から上げていく.C:どう考えてもセット内最難…

CODECHEF LUNCHTIME37

これやってたらSRMレジりミスった.LCOLLIS:やるだけ OMWG:O(1) SQNUMBF: 100個のlong longの積が4以上の平方数で割れるかどうか.素数p^2のみ考えれば良い.pが2つの整数にまたがっている場合は,gcdを取ればpが出てくるのでわかる.1つの整数の場合は,10^6まで…

ARC056

最近ブログ書いてなかったので備忘録的に書いておこうかなり反省した。A:書いてそのまま出したら最後K個買ったほうが安いのを忘れていてWAB:割とすんなり後ろからunionfindが思いつけてよかった.(xに行くとき,x未満は全て埋まっているとして良い.(a(

ICPC国内予選2016

Sleep 18000 (wafrelka,wo,sigma)で出ていました. チーム戦とはいえはじめてコンテストで一位取った気がするので嬉しいです.A:例年より問題文も読みやすくて簡単だった B:wafrelkaがやった C:woがやった D:DP E:いつもの少し面倒なdfs はじめいろいろ間違っ…

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&leq;100,M&leq;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>…