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…
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>…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314構文解析といえばこの問題みたいなところあるよね。まず左再帰を取り除きます。assignment ::= var "=" expr "." var ::= "A" | "B" | "C"expr ::= term expr' expr' ::= "+" term expr' | "-…
https://beta.atcoder.jp/contests/arc101本番解けないと意味ないってそれ一番。 コンテスト中は1完です…C K個の連続した区間になるので適切に計算すればO(N)。 D 本番誤読してかなしぃ。中央値はやっぱりにぶたんなんだよなぁ。 https://agc006.contest.atc…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255優先順位が低い演算子から再帰していく感じでやればいいです。例えば演算子の優先順位が(),/,*,-,+だったら、expr0::=expr0 + expr0 | expr1 expr1::=expr1 - expr1 | expr2 expr2::=expr2 * …
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155&lang=jp構文解析おもしろいじゃーん。関数の返し値をpair ( (値),(どこまで解析したか) )にして、引数を(どこから解析するか)にすれば簡単に実装できます。 今回は formula:=-formula|(formu…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021&lang=jpは?これも難しくないか? 普通にO(MN)頂点O(MN^2)辺のグラフでダイクストラすればいいんですが、これだと若干重くないか?ということで、O(N^3)解法にしました。Aから中継点を数カ所挟…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011&lang=jpは?むずくないか? DPできないと思ったので、貪欲でやりました。 うしろから見ます。k日間でできるとします。k日目スケジュールが入っている人の集合をSとします。k-1日目でSに全部の…
https://codeforces.com/contest/1019Aで無限に時間を使ってしまい、絶望的だったので撤退…いやでも今後のためにも提出したほうがよかったかなぁ…A 普通に勝たせる人に何票入れるかで全探索すれば良いんですが、いろいろこんがらがってしまいだめでした… B …
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2383350なのに全然解けない…と思ったら誤読で悲しかったです。 でも誤読した問題も少しおもしろいので紹介したいと思います。今までプレイした最高難易度と同じもしくは簡単な問題を解くことがT回…
https://codeforces.com/contest/949ABしか解けないよぉ助けてくれA 最大のzebraを取っていけばいいことはわかりますが、実装にてこずりました。こういうのはsetって一番言われてる。 B 再帰的に求めていけばいいです。 C 最近有向グラフの問題といてなくて…
