https://atcoder.jp/contests/agc029/tasks冷えました…A 結局はWを動かす操作です。 B 面白い。1,2,3,....2^30のグラフを考えると、明らかに木です。問題のグラフは明らかにこのグラフの部分グラフなので森です。 あとはgreedyに取っていけばいいです。ただ…

https://codeforces.com/contest/1092だいぶ調子良かった。A WA on test1やったw B sort C 長さN-1の文字列がほぼ答え。 D1 解いてないけど偶奇は見えた。 D2 一番短いものからやっていって、連結サイズが奇数になったらダメ。 E これとけたのいいねえ。ある…

https://codeforces.com/contest/1090/problem/J考察有りライブラリ使いまくりで楽しい。 まず文字数を固定します。するとTを少しずつずらした時何通り同じ文字列があるかみたいな問題になります。 こんな感じです。 Tを1文字shift S:aadaa | T: aaaaaba| 文…

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

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

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

当分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無駄に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…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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…

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

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

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

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

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