AtCoder Grand Contest 041 D. Problem Scores

自分用メモなので簡略に書く 最近気づいたけどlatex記法より手書き+写真のほうが早いぜ d1を便宜上置くと、次元が1つ減ってdpが簡単にできるようになるのかなり気持ち悪いと思います、思いませんか?

第一回日本最強プログラマー学生選手権予選 F. Candy Retribution

これ1000点じゃないだろ 問題概要 読んで: F - Candy Retribution 解法 条件を満たす昇順の列 に対して、それを並べる方法は通りある。 ここでは にが個含まれることを指す。 よって、dp[x][y] := 「y個からなる列を考えた時、それらの和はxとなっているもの…

AtCoder Grand Contest 013 E. Placing Squares(+open problem)

問題概要 読んで: E - Placing Squares 解法 とりあえず置いてはいけない箇所の制約を無視する。 とおけば、置いてはいけない場所がなかった状態での求めるべき値は の の係数。 であるからまあとしてもよい。 さて、具体的にこの関数の 次の係数を とすると…

AtCoder Regular Contest 077 F. SS

本質的な補題を証明してから解いたら3時間ぐらいかかった。 解説見たらその部分「周期の最小性より」で省略されてたけど、そんな単純に成り立つものだと僕は思えてないんだよね、そんな簡単に証明できる??? ということで補題と証明を以下に書きます。 補…

AtCoder Grand Contest 018 D. Tree and Hamilton Path

誤読したら解けたんだけど(は?)、未証明が発生した。 問題概要 読んで: D - Tree and Hamilton Path 解法 まず誤読した問題を書きます: 最長のHamilton Cycleを求めてください。 これは多分900点ぐらいです、以下に解法を書くので考えたい人は先に考えてく…

AtCoder Grand Contest 023 B. Find Symmetries

問題概要 B - Find Symmetries 解法 NxNの盤面を四方に無限に繰り返し並べて、無限に広がる平面を考えても差し支えない。 ここで、y=x+cの直線をイメージすれば、同じ直線が通るマスは、「良い盤面であるかどうか」が一致する事が分かるので、O(N)個のマスで…

AtCoder Grand Contest 014 B. Unplanned Queries

とても面白かった。典型的な"よく考えると自明"な問題な気がする。 今見てみたらあっさり解けたんだけど、この前問題を見た時は20分ぐらい考えて、「は??本当に500点か???」とキレながら諦めた覚えがある。別に今でもこの問題が簡単だとは思ってないし…

AtCoder Regular Contest 067 E. Grouping

もしかしてなんですけどmaroon君が苦手ですか?maroon君がセッターの時は出ないようにします。 問題 読めばええ: E - Grouping 解法 まあどう見てもDP。 初め人を区別しないと思っていて(どうして?)、詰んだ。 というより全然違う立式をしていた。 人を区別…

AtCoder Regular Contest 083 D. Restoring Road Network

結構面白かった。 問題 読んで: D - Restoring Road Network 解法 Warshall-Floyd法を考えれば、与えられたテーブルが条件を満たしているかは、Warshall-Floyd法内で行う更新を行っても値が変化しなければ良いことが分かるので、こっちは自明。 問題はグラフ…

AtCoder Regular Contest 072 D. Alice&Brown

すんなり解けた割に納得がいかなかった。今日結構500点問題色々見たけど、安定しないなあと思うし本当によくこれで赤色目指すみたいな気持ちでいれましたねみたいな感じ。 問題文 読んで: D - Alice&Brown 解法 正直なんで解けたのか分かっていない。なんで…

AtCoder Grand Contest 013 B. Hamiltonish Path

頭が悪すぎて絶望したので反省に書いておく。 この問題の概要を読んだのは3週間前とかで、今まで普通に解けていなかったし、結局 さっきAcceptはしたものの嘘解法であることに気づいたし最悪。 500点問題もまともに解けないとかもはや、やってる意味はあるん…

AOJ 0581 お土産購入計画 (Gifts)

2012年の情報オリンピック予選の6問目。当時解けなかったのは当然としても、今見ても結構つらい問題で、5年越しにようやくACしたのでなんとなくブログに書いておく。 問題文 まあ日本語なので読みましょう お土産購入計画 | Aizu Online Judge 解法 流石にbi…

符号でバグってそうだったら-Wsign-conversionも使おうねという話

TL;DR的にはタイトルまんまです。 CodeForcesでまあこんな感じで激冷えしてしまったんですが、 原因の一端に、自分がコンパイラオプションを正しく認識していなかった事もあった上、ほとんど日本語でも英語でも、似たような現象に悩まされてそうな人がいなか…

MP法とKMP法の違い

大学生なのでデータ構造とアルゴリズムという授業を取っているんですが、今まで自分がKMP法だと思い込んでいたものがMP法だった上、ネット上の記事が無限にバラバラなのでメモしておく。 MP法 MP法はMorris-Pratt algorithmと呼ばれるもので、Knuthが登場し…

Codeforces Round #415 (Div. 1) C. Find a car

dpの遷移が複雑すぎるだろ。 問題概要 縦109, 横109の合計1018個のマス目があり、上からi番目, 左からj番目のマス目を(i, j)と表す。マス目に以下のルールで数を書き込んでいく: マス(i, j)には、マス{(x, j) | 1 ≦ x < i}とマス{(i, y) | 1 ≦ y < j}に書か…

みんなのプロコン 2017 予選 D

みんなになれなかった。 問題概要 読んで: D: 工場 - 「みんなのプロコン」 | AtCoder 解法 正攻法はそのままこのクエリを実現しようとすれば結合則成り立つので値を2,3個持ってくださいというやつみたいです(たしかにね。)。 クエリの時系列と日数の時系列…

CTFのpoteti問題まとめ

どうも、binjaリーダーのpotetiです。あまりしたくはありませんが、Twitterを見ていて必要性を感じたのでCTFの話をします。 CTFのExploitation(Pwnable)ジャンルで、過去にpotetiが作問した問題はいくつかあって、通称bataリスト(だっけ?)と呼ばれる例のあ…

Codeforces Round #176 (Div. 1) D. Tourists

JOIerお家芸感。なんかこれはJOIerは結構見た瞬間簡単だなあと思う気がする。おそらくDではない。 原点にある点がn個あり、i個目の点は時刻q[i]に原点を出発し、x軸の正方向に沿って速さ1で進む。また、それとは別にm個の線分が存在して、i番目の線分は時刻t…

Codeforces Round #176 (Div. 1)

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 Round #127 (Div. 1)

codeforces.com tourist回嫌い(直球) 色々やってしまい1完でした。 A. 以下の様な条件を満たす行列を考える。 n*nの正方行列である 全ての要素が0または1 行列は上下左右対称すなわちAi, j = An - i + 1, j and Ai, j = Ai, n - j + 1が成り立つ 上下左右に…

Codeforces Round #177 (Div. 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,queueの実装

出来上がったと思うので一応うp 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…

scanf

後輩の質問を受けた。 中1は基本的にC言語かJavaの勉強をしていて、AOJ解けって言ってた。 「AOJのVolume5の501がわかりません」 要は、文字列を変換するリストと、文字列が与えられるので変換後の文字列を出力しろと(nの上限決まってなかったりで疑問なんだ…

stackの実装(続き)

とりあえず実装出来ました。 やっちゃいけないことしてる感があるのと、これでもまだ不完全なのが…(というか、なんで俺はC++使わない縛りをしているんだ? #define make_stack(x) stack x;x.last=NULL#define make_stack_p(x) stack *x=(stack*)malloc(siz…

AIZU ONLINE JUDGE 10000

+++++++++[>++++++++>+++++++++++>++++>++++++++++>+++++++++++>+<<<<<<-]>.>++.+++++++..+++.>----.>---.<<.+++.------.>>>+.>+.