SRM埋め(4)

わりとeasyうまくなってきたし、easyとmediamともに残っているセットを残しておきたいので、mediam練習します。SRM 732 mediam, hard 2問ともsurreal numberとかいう競プロではあまり馴染みのない道具を使う。知ってる人は一瞬だけど知らない人は絶対解けな…

最小全域木

この記事はhttps://adventar.org/calendars/3598の6日目の記事として書かれました。昨日の記事はsatosさんの独断と偏見による根津/本郷飯事情でした。 19erのomochana2というものです。 最小全域木を扱う際で有効な定理を紹介したいと思います。めっちゃ数学…

SRM埋め(3)

SRM 714 easy easyはこれくらいの難易度が良いよなぁ。何ターン目までに消さないといけないという条件が求まる。SRM 713 easy 難しい。保留->わかったんですけど、easyにしては実装複雑すぎでは?と思ってkmjpさんの解説記事見たら全く同じでおったまげました…

SRM埋め(2)

当分easyで鍛えます。(気分でmedときます)scoreですが目安としては 5分で満点*0.95 10分で満点*0.9 15分で満点*0.8 20分で満点*0.7 36分で満点*0.5 と覚えておけばよいでしょう。早解きは正義。SRM 730 easy 「「「「「non decreasing」」」」コードは1発で…

SRM埋め

最近のSRM無駄にconstructive多いっすね。 SRM 742 easy 1,0.5,0.25,0.125....と1,2,4,8,16....を作って適当に繋げれば良いけどバグった。 SRM 742 med kmpチックにbitdpすればいいSRM 740 easy どういうことやねんと思ったら罠が有りました… SRM 740 medium…

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

https://beta.atcoder.jp/contests/dwacon5th-prelimsアーA Nかけましょう。 B なぜかバグらせた…上からbit決めましょう。 C なんで思いつかなかったのかなぁ…ちゃんと順番決めて見ていかないからダメ。DとMの数もってしゃくとりすればいいです。 int N, Q; …

DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選

https://beta.atcoder.jp/contests/ddcc2017-qual/tasks去年の予選です。ばちゃコンしました。ABはい C set D とりあえず、対称な4マスずつに分けて考えれば良いことがわかります。 すると縦に対称、横に対称、3マス塗られている、4マス塗られているの4パタ…

「みんなのプロコン 2018」決勝B: 経路が色々

https://beta.atcoder.jp/contests/yahoo-procon2018-final/tasks/yahoo_procon2018_final_bたぶん想定解よりも思いつきやすい方法で。 base-3でやらず、base-2でやりました。例えばK=217(二進法で11011001)ならこのようにやります。 ........# .##.###.# ..…

yukicoder埋め

https://yukicoder.me/problems/no/753dp[level][bit][winner]:level段のトーナメントをbitに属す挑戦者で作る。勝者がwinnerの時の場合の数 として求めます。高速化いろいろしてAC。https://yukicoder.me/problems/no/749和と積のクエリが混ざっている時っ…

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1)

https://codeforces.com/contest/1074DEFを見ただけですが…D 区間をsetで持っておけば奈良市計算量決められるやつ。 E 気合としか言いようがない。基本2*2の回転でできますが、最後だけ2*3の回転をいれて調整します。 F euler tourすれば区間をたかだか3つ足…

Mail.Ru Cup 2018 Round 2

https://codeforces.com/contest/1055A ちょっと場合分けがあって面倒ですね。 B 幅1の区間しかたさないので、両脇見ればいいだけです。 C GCD D 良問。違う部分は共通じゃないと行けなくて(なぜかここにきづけなかった)、伸ばすだけ伸ばしてマッチしてほし…

Educational Codeforces Round 53

http://codeforces.com/contest/1073AB はい。 C にぶたん。 D 煩雑になるだろうなぁと思ったら、実は愚直な解法がO(NlogT)になっているという。良問。 何回も同じ値についてmodを取るとかなりの勢いで値が減っていくことがあんまり意識できてなかった。 E …

Codeforces Round #519 by Botan Investments

http://codeforces.com/contest/1043/problem/FAB うん C 前から塊になるようにやれば。 D SAつかって殴った。TLEめちゃくちゃギリギリ。解説は並び替えてやってますね。 E a-bでsortすれば。 F 良問。まず数え上げに帰着して、包除原理する。このタイプ久し…

VK Cup 2018 - Round 1

http://codeforces.com/problemset/problem/923/DA 良問。どこまで減らせるかが貪欲で求まる。 B 雪山について独立に考えれば。 C よくあるbitのやつ。これtrieでやるのかなぁ…segtreeっぽくしちゃったけど。また使いそうなので貼っときます。 int K = 1; st…

New Year Contest 2015

https://snuke21.contest.atcoder.jp/tasks/snuke21_e懐かしの。ムズイ。 ->初手でいけそうなのが、強連結の条件を考えてみるだけだった。 ->強連結成分がL個以上ならまあまあできそう。これが求まればあと引き算するだけ。 -->N!Σ(n+m+...=N)(2^(n(n-1)/2) …

ARC100F: Colorful Sequences

https://beta.atcoder.jp/contests/arc100/tasks/arc100_d考えること多すぎ。 ->とりまどうやって数え上げるか考える。 -->colorfulな列を考えて、そこにAが何個あるか? -->i番目からAが始まる列がcolorfulな場合の数Fiを計算する? -->まあ後者だろう。 ->co…

SoundHound Programming Contest 2018 Masters Tournament,C: Not Too Close

https://soundhound2018-summer-final-open.contest.atcoder.jp/tasks/soundhound2018_summer_final_cわりとすっきり解けた気がする。思考プロセス書きます。N,D ->分割統治? ->直線にしてみる? ->とりあえず緩和して最短距離がD以上のグラフの個数を数えて…

AGC028

https://agc028.contest.atcoder.jp/A map使った。 B 方針ミスって式が複雑になってダメでした…。式で考察するのが苦手すぎる。 てか式で考察が進むことはあまりないんだよなぁ。 C 結構場合分けがあって難しいと思う。1発で通してる人はすごい。 D おそらく…

AGC027

https://beta.atcoder.jp/contests/agc027virtual contestしました。やっぱり時間制限無しでやるのと全然緊張感が違う…A うん。 C 行き先がAのみとかBのみになるとヤバイので、そういう点を取り除いていく。 B 焦って、連続した区間でゴミを取っていけばいい…

JOI埋め(難易度10)

BIT

結構骨がある問題ばっかで面白い。SALT TREE XV 点と辺がともに偶数の時負けであることを示しに行く。やっぱりGameは負けの条件を考えて、(勝ち->負けに必ず落とし込める+負け->負けと遷移できない)を示すのが定石ですね。必要条件から狭めていく感じと同じ…

ARC103

https://arc103.contest.atcoder.jp/assignmentsF Open- >それっぽい考察はできたけど、Dが同じ値を複数持つ時どうするんだ…- >問題文「Dの値は全て異なる」 - >実装完了。この時点で75分で、300+300+700勢に勝てなさそうなので撤退…C これ難しくないか?実装…

AOJ 1181

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jpものを回転させる問題は他にも http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2169 がありますが、置換で回転をあらわす時の注意事項。 例えば、 (0, 1, 2, 3, 4, 5) (4…

JOI埋め(難易度9)

AOJ/AtCoder-JOI9はそんなに難しくはないですね。 実装が多めなのを考慮してもatcoderで言えば600-700くらい?Typhoon 平面探査 Stamps pairでdp Abduction xy独立です。 Ski にぶたん Chopsticks うわぁこれは反省。区間dpということは両端の値が本質的にな…

CODE FESTIVAL 2018 qual A+オマケ

DP

https://beta.atcoder.jp/contests/code-festival-2018-quala通過です…A sortしたけど、要素が3つでなんかオーバーキルな気がしてしまう B 愚直にやった。sortもしてません C まあdpだよね。0にならないとKを減らせないので注意。 D まあdpだよね。BIT使った…

AGC003F

https://agc003.contest.atcoder.jp/tasks/agc003_f非連結だと勘違いしてハマってた…まず縦に並べても横に並べても繋がる場合は答えが1です。 どっちもつながらない場合は#の個数をPとしてP^(K-1)です。 問題は片方だけ繋がる場合です。今回は横に繋がるとし…

AGC001F

https://agc001.contest.atcoder.jp/tasks/agc001_fわりと自然な考察で解けるからそんな難しくはないけど…でもおもしろいのは確か。解説にあるとおりトポロジカル順を求めれば良いんですが以下はその具体的な方法です。 (i,A[i])のようにplotします。 [i,i+k…

AOJ 2382

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2382証明がむずい。地雷。絶対450じゃない。数オリメダリストの力を借りました。まず隣接してる頂点同士を結んで木を作ります。この木の辺の数をfとしましょう。 f=N-1の時、全ての頂点が直接的or…

ARC102

https://beta.atcoder.jp/contests/arc102/tasksC K/2が肝とわかれば。 D 2^nの辺を張って、適当に付け加えれば良さそうと思って実際そうでした。添字がめんどい。 int L; vector<pi> G[20]; void solve() { cin >> L; int N = 1; while(L >= (1 << N)) N++; rep</pi>…

AOJ 1314

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314構文解析といえばこの問題みたいなところあるよね。まず左再帰を取り除きます。assignment ::= var "=" expr "." var ::= "A" | "B" | "C"expr ::= term expr' expr' ::= "+" term expr' | "-…

ARC101

https://beta.atcoder.jp/contests/arc101本番解けないと意味ないってそれ一番。 コンテスト中は1完です…C K個の連続した区間になるので適切に計算すればO(N)。 D 本番誤読してかなしぃ。中央値はやっぱりにぶたんなんだよなぁ。 https://agc006.contest.atc…