コンテストへのリンク 参加しました。結果は以下です。 A - Road To Zero 問題概要 解説 B - Binary Period 問題概要 解説 C - Yet Another Counting Problem 問題概要 解説 D - Multiple Testcases 問題概要 A - Road To Zero 問題概要 を するのに＄かかる…

AtCoder、AtCoder Beginner Contest、D - Multiple of 2019、E - Two Currencies、拡張ダイクストラ、競技プログラミング

A. Nastya and Rice 問題概要 実装 B. Nastya and Door 問題概要 解説 実装 C. Nastya and Strange Generator 問題概要 実装 D. Nastya and Scoreboard 問題概要 解説 実装 A. Nastya and Rice 問題概要 一つ重さの粒が個あり、その和がである場合、粒の重さ…

Google Code Jam 競技プログラミング 解説

問題へのリンク 問題 グリッド上に人が人いる。南北東西どちらかの方向を向いている。 例えば、東を向いている人は、西にはいけないが、他はどの方向にも行ける。人の通りうる数が最大の座標を求めよ。 解法 軸ごとに独立に考えてよい。それぞれの最大座標が…

A. Wrong Substraction B. Two-gram C. Less or Equal D. Divide by three, multiply by two E. Cyclic Components F. Consecutive Subsequence 参考 A. Wrong Substraction 間違った引き算アルゴリズムを愚直に実装します。 B. Two-gram 連続する二文字の最…

D. Xenia and Colorful Gems 問題へのリンク D. Xenia and Colorful Gems 問題概要 制約 解説 すべてまとめてソートする 提出 問題概要 から一つずつ数を選び、としたとき、 とする。の最小値を求めよ。 制約 解説 方針として、 真ん中を固定して、左右を二…

コンテストへのリンク Codeforces Round #635 (Div. 2)に参加しました。結果は以下の通り、4完でした。レートは+55で、1681に伸びました。思った以上に解けたので満足です。D問題は終了3分前にACしてアドレナリンドバドバでした。 A. Ichihime and Triangle …

C. Linova and Kingdom 問題へのリンク C. Linova and Kingdom 問題概要 制約 解説 問題概要 頂点を根とする頂点数の木がある。最初、頂点の色はすべて白の状態から、個の頂点を黒く塗る。黒色の点から、根までの最短路で、白の点を通る数を最大化したい。塗…

問題が複雑な場合は、簡単な問題に落として考える 貪欲の簡単な証明 簡単な貪欲の反例の見つけ方 単純に考える 再帰は数学的帰納法である 定式化の手法 再帰的な構造 引用元 問題が複雑な場合は、簡単な問題に落として考える グラフ -> 木 二次元 -> 一次元 …

B - Pascal Walk 問題へのリンク 和がになるようにパスカルの三角形上を動く問題。 解説 以降、とする。 パスカルの三角形の行の和は二冪であることから、を2進数表現すればうまく表せそうである。ここで、r行に到達したいだけでも、その手前の行を訪れなけ…

Google Code Jam 2020 Round 1Aに参加しました。 A - Pattern Matching B - Pascal Walk C - Square Dance abしか解けませんでした。精進します。 順位表 A - Pattern Matching 各文字列をでsplitし、最初と最後の要素、つまりprefixとsuffixに注目して議論…

問題へのリンク 問題概要 制約 解説 問題概要 問題が問あり、番目の問題のスコアはである。人が独立に問選び、それらのスコアをずつ上げる。人の選択後、スコアの降順に並べられ、最初の問が採用される。採用される可能性のある問題は何問あるか？ 制約 解説…

公式想定解と異なる解き方をしたので共有します。 問題概要 解説 方針 DPの定義、初期化、遷移 定義 初期化 遷移 実装 問題概要 問題へのリンク 正の整数が以下の条件を満たすとき、はルンルン数であるといいます。 Xを(leading zeroなしで)十進数表記した際…

参加しました。3完で緑パフォ、緑に戻りました。水切り楽しいですね。 E、Fは読んでないのでそのうち復習します。 My Submissions C chokudaiさんのすごろくの考え方が面白かったです。 C問題、数学の問題といえばそうなんだけど、「無限に長いすごろくがあ…

問題概要 問題へのリンク の盤面が与えられます。個の箱が座標に積み上げられている盤面を初期盤面と呼びます。以下の処理を繰り返し、すべての盤面の高さを揃えるゲームをします。 2つの隣り合う箱の上に一つずつ箱を積み上げる 一つの箱の上に二つの箱を積…

参加しました。3完で3883位(rated内)で、レート1626(-20)になりました。ギリギリ青をキープです。 順位表 A. Exercising Walk a = b のとき a != b のとき B. Composite Coloring C. K-Complete Word D. Walk on Matrix E - Height All the Same 参考 A. Exe…