有理数問題とは 精度の関係でdoubleで保持するのではなく、有理数の形（分数の形）で計算結果を保持したほうがいいときがある pythonとかで高精度でやる方法もあるし、有理数ライブラリを持っておくと有利な場面もある 問題 AC Grand Election SRM761 Div1 E…

競技プログラミングにおける有理数問題まとめ

https://atcoder.jp/contests/abc131/tasks/abc131_e 解説 https://atcoder.jp/contests/abc131/submissions/6082165こういう構築系は、最小ケースと最大ケースを考えるのが、常套テクである。 最小ケースは完全グラフを作ればK=0にできる。最大ケースはスタ…

Friendships [AtCoder Beginner Contest 131 E]

https://atcoder.jp/contests/abc131/tasks/abc131_d 前提知識 区間スケジューリング 解説 https://atcoder.jp/contests/abc131/submissions/6077645この問題はほぼ区間スケジューリング問題である。 区間スケジューリングを解くには終了時間が最も早い仕事…

Megalomania [AtCoder Beginner Contest 131 D]

https://atcoder.jp/contests/abc131/tasks/abc131_c 解説 https://atcoder.jp/contests/abc131/submissions/6076233常套テクとして「区間[a,b]の個数は区間[1,b]の個数-区間[1,a)の個数」というのがある。 （今日の北陸アルゴリズム勉強会でtorusさんが言っ…

Anti-Division [AtCoder Beginner Contest 131 C]

https://atcoder.jp/contests/abc131/tasks/abc131_b 解説 https://atcoder.jp/contests/abc131/submissions/6074212食べるリンゴを全探索する。 N個のリンゴすべてを材料としてできる味と、リンゴi以外を材料としてできる味の差は L + i - 1である。 差の絶…

Bite Eating [AtCoder Beginner Contest 131 B]

https://atcoder.jp/contests/abc131/tasks/abc131_a 解説 https://atcoder.jp/contests/abc131/submissions/6073193条件にある通りに連続する数字があるかを判定する。 3通りあるので、ループしてもいいし、そうじゃなくてもいい。 string S; //-----------…

Security [AtCoder Beginner Contest 131 A]

https://yukicoder.me/problems/no/79 解説 https://yukicoder.me/submissions/353422cnt[i] := レベルがiであるユーザー数 を計算しよう。 あとは、これを使って、cnt[i]が最大で、かつ、その中でiが最大のものを答えると答え。 int N, L[101010]; int cnt[…

過小評価ダメ・ゼッタイ [yukicoder No.79]

https://www.facebook.com/hackercup/problem/589264531559040/ 提出 前提知識 構文解析 解説 https://codeforces.com/gym/102249/submission/55747916とっても難しそうな問題に見えるので、エスパーしよう。 x=false, x=trueの時を評価して、どちらも同じ結…

Mr. X [Facebook Hacker Cup 2019 Qualification Round C]

https://www.facebook.com/hackercup/problem/2426282194266338/ 提出 解説 https://codeforces.com/gym/102249/submission/55747853Leapfrog: Ch. 1に加えてyesの条件が増えるが、bが2以上であれば、カエルは行ける。 ABB.. AB.B. .BAB. .B.BA ..BBA .ABB.…

Leapfrog: Ch. 2 [Facebook Hacker Cup 2019 Qualification Round B]

https://www.facebook.com/hackercup/problem/656203948152907/ 提出先 解説 https://codeforces.com/gym/102249/submission/55747583A以降のマスの個数をn, 最小限必要なBの個数をbとすると、以下のような表になる。 n b 2 1 3 2 4 2 5 3 6 3これをみると、…

Leapfrog: Ch. 1 [Facebook Hacker Cup 2019 Qualification Round A]

https://atcoder.jp/contests/abc130/tasks/abc130_e 動的計画法 動的計画法 解説 https://atcoder.jp/contests/abc130/submissions/6001273mod10^9+7で制約が10^3くらいなので、dp[10^3][10^3]かなーと経験則的に思う。 2つの数列があって、dp[s][t]である…

Common Subsequence [AtCoder Beginner Contest 130 E]

https://atcoder.jp/contests/abc130/tasks/abc130_d しゃくとり法 解説 https://atcoder.jp/contests/abc130/submissions/6000372微妙に何から手を付ければいいか分からない。 こんなときは全探索対象を探す訳だが、ここにも典型テクがある。 条件を満たす…

Enough Array [AtCoder Beginner Contest 130 D]

https://atcoder.jp/contests/abc130/tasks/abc130_c 解説 https://atcoder.jp/contests/abc130/submissions/6000248ABC300点問題なので、なるべく単純に考えることにする。 この問題はある種の構築問題である。 構築問題の典型テクとして「理論値の最大値を…

Rectangle Cutting [AtCoder Beginner Contest 130 C]

https://atcoder.jp/contests/abc130/tasks/abc130_b 解説 https://atcoder.jp/contests/abc130/submissions/6000104跳ねる動きをシミュレートする。 N≦100なので、シミュレートしても間に合う。 int N, X, L[101]; //-------------------------------------…

Bounding [AtCoder Beginner Contest 130 B]

https://atcoder.jp/contests/abc130/tasks/abc130_a 解説 https://atcoder.jp/contests/abc130/submissions/6000049問題文の通りに分岐して解く。 int X, A; //-----------------------------------------------------------------------------------------…

Rounding [AtCoder Beginner Contest 130 A]

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b 前提知識 UnionFind 解説 https://atcoder.jp/contests/diverta2019-2/submissions/5943792なにか全探索対象を探す。 どこを全探索しようかなと色々考える。 1つ目を全探索すると、自由度…

Picking Up [diverta 2019 Programming Contest 2 B]

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_a 解説 https://atcoder.jp/contests/diverta2019-2/submissions/5943412まず、みんなボールは1個以上受け取るので、先に渡しておこう。 最大-最小を最大化したいのだが、最小は0にすればい…

Ball Distribution [diverta 2019 Programming Contest 2 A]

https://yukicoder.me/problems/no/840 前提知識 行列累乗によるDP高速化 DPテク11「文字列の部分列の個数を添え字に持つ典型」 解説 https://yukicoder.me/submissions/352662Nが大きい、かつ、数え上げということなので、まずは行列累乗路線で考える。 「…

ほむほむほむら [yukicoder No.840]

https://yukicoder.me/problems/no/838 前提知識 DPテク17「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」 解説 https://yukicoder.me/submissions/352656まず、前の問題が解けないと解けないので、こちらを理解する。 get(L, R)…

Noelちゃんと星々3 [yukicoder No.838]

https://yukicoder.me/problems/no/837 前提知識 「マンハッタン距離の差の和の最小値は中央値に集めるとき」 解説 https://yukicoder.me/submissions/352655マンハッタン距離の総和の最小値の地点は中央値であるというテクを使う。 高さの変更先は2つあると…

Noelちゃんと星々2 [yukicoder No.837]

https://yukicoder.me/problems/no/836 解説 https://yukicoder.me/submissions/352484自分はライブラリにしてあるので、貼るだけ。 countMultiple(L, R, div, mod) := [L,R]の間の数でdivで割ったときの剰余がmodである個数 これを作るが、区間の数を[L,R] …

じょうよ [yukicoder No.836]

https://yukicoder.me/problems/no/835 解説 https://yukicoder.me/submissions/352483小数はちょっと扱いにくいので、ジュースを2本で3Lと考えよう。 すると、N/2の切り捨て分だけ3L手に入るので、N/2*3本はある。 あとは、Nが奇数であれば、+1.5L分なので…

ジュース [yukicoder No.835]

https://ctftime.org/writeup/15644 前提知識 難読化ページへの対処（Chromeのデベロッパツールでなんとかする） ARIA 解説 ほぼこれの和訳記事です。おしゃれなサイトが出てくる。 色々入力してみるがi love 0やらi love 1やら出てくる。 ソースを見てみる…

Accessible Rich Internet Applications [HSCTF 6 web]

https://ctftime.org/task/8693 前提知識 PHP Type Juggling, Magic Hash 解説 md5でハッシュ化したときに自分と同じハッシュになるものを探して答えよという問題。 そんなものあるのかという感じであるが、==を使った比較をしているので、 PHP Type Jugglin…

md5-- [HSCTF 6 web]

https://atcoder.jp/contests/abc129/tasks/abc129_e 前提知識 桁DP 解説 https://atcoder.jp/contests/abc129/submissions/5869998a + b = a xor b これを読み替えると、a & b = 0となる。 つまり、 a + b ≦ L かつ a & b = 0を満たすa,bの組を数えればいい…

Sum Equals Xor [AtCoder Beginner Contest 129 E]

https://atcoder.jp/contests/abc129/tasks/abc129_d 解説 https://atcoder.jp/contests/abc129/submissions/5860261明かりを置くマスを全探索すればいい。 するとこの時点で計算量がO(HW)なので、既にギリギリである。 なのでO(1)かO(logH)とかになる。 明…

Lamp [AtCoder Beginner Contest 129 D]

https://atcoder.jp/contests/abc129/tasks/abc129_c 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc129/submissions/5860105組み合わせ問題でmod10^9+7なので、とりあえずDPできないか考える。 dp[i] := i段目にたどり着くまでの移動方法の組み…

Typical Stairs [AtCoder Beginner Contest 129 C]

https://atcoder.jp/contests/abc129/tasks/abc129_b 解説 https://atcoder.jp/contests/abc129/submissions/5859689グループの分け方はN-1通りあるので、それを全探索して、差の絶対値の最小値を求める。 2つのグループに分けたあと、それぞれの重さの和を…

Balance [AtCoder Beginner Contest 129 B]

https://atcoder.jp/contests/abc129/tasks/abc129_a 解説 https://atcoder.jp/contests/abc129/submissions/5859544考えられるパターンはP+Q, P+R, Q+Rの三択なので、 最小のものが答え。 int P, Q, R; //------------------------------------------------…

Airplane [AtCoder Beginner Contest 129 A]

https://ctftime.org/task/8651We setup this PDF conversion service for public use, hopefully it's safe.http://challenges.fbctf.com:8084 前提知識 XXE 解説 他の解説を見たが、実際に解いたかのような動きで書く。サイトには「Choose a file to uploa…

pdfme [Facebook CTF 2019 web 655]