想定解はフローだが、離散凸解析をちょっと知っていると、目的関数がM凸なので、交換を繰り返すと解けることが分かる。 実際、Benqは本番これで通しているらしい これを証明する。 問題文中で定義されている目的関数をfとする。これがM凸であることを示す。 …
自分用メモなので簡略に書く 最近気づいたけどlatex記法より手書き+写真のほうが早いぜ d1を便宜上置くと、次元が1つ減ってdpが簡単にできるようになるのかなり気持ち悪いと思います、思いませんか？
これ1000点じゃないだろ 問題概要 読んで: F - Candy Retribution 解法 条件を満たす昇順の列 に対して、それを並べる方法は通りある。 ここでは にが個含まれることを指す。 よって、dp[x][y] := 「y個からなる列を考えた時、それらの和はxとなっているもの…
問題概要 読んで: E - Placing Squares 解法 とりあえず置いてはいけない箇所の制約を無視する。 とおけば、置いてはいけない場所がなかった状態での求めるべき値は の の係数。 であるからまあとしてもよい。 さて、具体的にこの関数の 次の係数を とすると…
本質的な補題を証明してから解いたら3時間ぐらいかかった。 解説見たらその部分「周期の最小性より」で省略されてたけど、そんな単純に成り立つものだと僕は思えてないんだよね、そんな簡単に証明できる？？？ ということで補題と証明を以下に書きます。 補…
誤読したら解けたんだけど(は？)、未証明が発生した。 問題概要 読んで: D - Tree and Hamilton Path 解法 まず誤読した問題を書きます: 最長のHamilton Cycleを求めてください。 これは多分900点ぐらいです、以下に解法を書くので考えたい人は先に考えてく…
問題概要 B - Find Symmetries 解法 NxNの盤面を四方に無限に繰り返し並べて、無限に広がる平面を考えても差し支えない。 ここで、y=x+cの直線をイメージすれば、同じ直線が通るマスは、「良い盤面であるかどうか」が一致する事が分かるので、O(N)個のマスで…
とても面白かった。典型的な"よく考えると自明"な問題な気がする。 今見てみたらあっさり解けたんだけど、この前問題を見た時は20分ぐらい考えて、「は？？本当に500点か？？？」とキレながら諦めた覚えがある。別に今でもこの問題が簡単だとは思ってないし…
もしかしてなんですけどmaroon君が苦手ですか？maroon君がセッターの時は出ないようにします。 問題 読めばええ: E - Grouping 解法 まあどう見てもDP。 初め人を区別しないと思っていて(どうして？)、詰んだ。 というより全然違う立式をしていた。 人を区別…
結構面白かった。 問題 読んで: D - Restoring Road Network 解法 Warshall-Floyd法を考えれば、与えられたテーブルが条件を満たしているかは、Warshall-Floyd法内で行う更新を行っても値が変化しなければ良いことが分かるので、こっちは自明。 問題はグラフ…
すんなり解けた割に納得がいかなかった。今日結構500点問題色々見たけど、安定しないなあと思うし本当によくこれで赤色目指すみたいな気持ちでいれましたねみたいな感じ。 問題文 読んで: D - Alice&Brown 解法 正直なんで解けたのか分かっていない。なんで…
頭が悪すぎて絶望したので反省に書いておく。 この問題の概要を読んだのは3週間前とかで、今まで普通に解けていなかったし、結局 さっきAcceptはしたものの嘘解法であることに気づいたし最悪。 500点問題もまともに解けないとかもはや、やってる意味はあるん…
2012年の情報オリンピック予選の6問目。当時解けなかったのは当然としても、今見ても結構つらい問題で、5年越しにようやくACしたのでなんとなくブログに書いておく。 問題文 まあ日本語なので読みましょう お土産購入計画 | Aizu Online Judge 解法 流石にbi…
TL;DR的にはタイトルまんまです。 CodeForcesでまあこんな感じで激冷えしてしまったんですが、 原因の一端に、自分がコンパイラオプションを正しく認識していなかった事もあった上、ほとんど日本語でも英語でも、似たような現象に悩まされてそうな人がいなか…
大学生なのでデータ構造とアルゴリズムという授業を取っているんですが、今まで自分がKMP法だと思い込んでいたものがMP法だった上、ネット上の記事が無限にバラバラなのでメモしておく。 MP法 MP法はMorris-Pratt algorithmと呼ばれるもので、Knuthが登場し…
dpの遷移が複雑すぎるだろ。 問題概要 縦109, 横109の合計1018個のマス目があり、上からi番目, 左からj番目のマス目を(i, j)と表す。マス目に以下のルールで数を書き込んでいく: マス(i, j)には、マス{(x, j) | 1 ≦ x < i}とマス{(i, y) | 1 ≦ y < j}に書か…
みんなになれなかった。 問題概要 読んで: D: 工場 - 「みんなのプロコン」 | AtCoder 解法 正攻法はそのままこのクエリを実現しようとすれば結合則成り立つので値を2,3個持ってくださいというやつみたいです(たしかにね。)。 クエリの時系列と日数の時系列…
JOIerお家芸感。なんかこれはJOIerは結構見た瞬間簡単だなあと思う気がする。おそらくDではない。 原点にある点がn個あり、i個目の点は時刻q[i]に原点を出発し、x軸の正方向に沿って速さ1で進む。また、それとは別にm個の線分が存在して、i番目の線分は時刻t…
codeforces.com はいサイアクの1完。 Bが分からない時は本当に辛いンゴねえ A. nが与えられる。1~nの順列P[1]~P[n]が「∀i(1 <= i <= n) P[P[i]] = n+1-i」を満たす。このようなPを1つ出力せよ。そのようなPがなければ-1と出力すること。 順列なのでグラフで…
codeforces.com tourist回嫌い(直球) 色々やってしまい1完でした。 A. 以下の様な条件を満たす行列を考える。 n*nの正方行列である 全ての要素が0または1 行列は上下左右対称すなわちAi, j = An - i + 1, j and Ai, j = Ai, n - j + 1が成り立つ 上下左右に…
codeforces.com 受験終わって初回virtual。3完。辛い。 A. k種類の小文字アルファベットから成るちょうど長さnの文字列であって、隣り合う文字が全て異なるものの内、辞書順最小のものは何か。 流石にaから始まるのが辞書順最小で、次は隣り合う文字は異なっ…
ブログ名が「死にたい」では不謹慎ではないかという声があったため「生きたい」に変更いたしました。
サ イ ボ ウ ズ 最 高 !!!
前書いたスタックを使って 前々から気になってた逆ポーランド記法に変換して処理する四則演算器書いた。 infix2postfix.h #include #include #include "stack.h"enum Priority {NIL, LOW, MIDDLE, HIGH,};static void check_argument(char **string, stack *…
出来上がったと思うので一応うｐ stack #define make_stack(x); stack x;x.last=NULL;#define make_stack_p(x); stack *(x)=(stack*)malloc(sizeof(stack));(x)->last=NULL;#define break_stack(x); while(top_stack(&x)!=0x00000000){pop_stack(&x);}#defin…
後輩の質問を受けた。 中1は基本的にC言語かJavaの勉強をしていて、AOJ解けって言ってた。 「AOJのVolume5の501がわかりません」 要は、文字列を変換するリストと、文字列が与えられるので変換後の文字列を出力しろと(nの上限決まってなかったりで疑問なんだ…
とりあえず実装出来ました。 やっちゃいけないことしてる感があるのと、これでもまだ不完全なのが…（というか、なんで俺はＣ++使わない縛りをしているんだ？ #define make_stack(x) stack x;x.last=NULL#define make_stack_p(x) stack *x=(stack*)malloc(siz…
+++++++++[>++++++++>+++++++++++>++++>++++++++++>+++++++++++>+<<<<<<-]>.>++.+++++++..+++.>----.>---.<<.+++.------.>>>+.>+.
