はまやんはまやんはまやん

hamayanhamayan's blog

2019-01-01から1年間の記事一覧

Strings with the Same Length [AtCoder Beginner Contest 148 B]

https://atcoder.jp/contests/abc148/tasks/abc148_b 解説 https://atcoder.jp/contests/abc148/submissions/9103093 ループを使って順番に出力していく。 特に難しい部分は無いが、文字列を扱うのが初めてだと戸惑うかもしれない。 C++であれば、文字列は配…

Round One [AtCoder Beginner Contest 148 A]

https://atcoder.jp/contests/abc148/tasks/abc148_a 解説 https://atcoder.jp/contests/abc148/submissions/9103058 ちょっとオーバーキルだが、setとかを使うと、あるかどうかが判別できる。 setは有無を判別する用途で使用できるというのを覚えておこう。…

Domino for Young [Codeforces Round #609 (Div. 1) B]

https://codeforces.com/contest/1268/problem/B 解説 https://codeforces.com/contest/1268/submission/67379641 天才力が試されている。 黒と白の市松模様でマスを塗ると、min(黒の個数, 白の個数)が答え。 int N, A[301010]; //-------------------------…

Long Beautiful Integer [Codeforces Round #609 (Div. 1) A]

https://codeforces.com/contest/1268/problem/A 解説 https://codeforces.com/contest/1268/submission/67379463 適当に解説を書いておく。 B[i] = A[i % K]としてまず置く。 先頭から大小関係を比較していく。 Bの方が既に大きいなら、答え。 Aの方が大き…

じゃんけん式 (Rock-Scissors-Paper Expression) [JOI2019/2020 二次予選ページ E]

https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_e 解説 https://atcoder.jp/contests/joi2020yo2/submissions/9043969 ICPCを感じる。 構文解析が要求される問題。 【20点】 知識ゼロでここまで通すのが相当難しい。 逆にここを超えられれば、考…

テンキー (Tenkey) [JOI2019/2020 二次予選ページ D]

https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_d 前提知識 幅優先探索 解説 https://atcoder.jp/contests/joi2020yo2/submissions/9040521 30点 mod 100000で固定されているが、例えばR=12345だった場合、 12345, 112345, 212345, 312345, ...…

桁和 (Digit Sum) [JOI2019/2020 二次予選ページ C]

https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_c 前提知識 yes/no系動的計画法 解説 https://atcoder.jp/contests/joi2020yo2/submissions/9040281 これは手法を知らないと、何も思いつかないかもしれない。 yes/no系の動的計画法で解ける。 dp…

いちご (Strawberry) [JOI2019/2020 二次予選ページ B]

https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_b 解説 https://atcoder.jp/contests/joi2020yo2/submissions/9040160 A,Tの上限が109なので、DPとかでなんとかするのは難しそう。 (座圧したらいけるかもしれないけど) なので、とりあえず最適…

ポスター (Poster) [JOI2019/2020 二次予選ページ A]

https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_a 解説 https://atcoder.jp/contests/joi2020yo2/submissions/9039879 操作が3種類あるが、大きく塗り替えと回転である。 時計回りに回転させてから、反時計回りに回転させるという動作は無駄なの…

Palindrome Factorization [EEIC Programming Contest #0 B]

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/palindromic-factorization 解説 https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/palindromic-factorization/submissions/code/1318660452 約数列…

Median Array [EEIC Programming Contest #0 C]

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/median-array 解説 https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/median-array/submissions/code/1318662405 色々な方針が見える。 ガチャに失…

C0unt [EEIC Programming Contest #0 E]

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/count-zero-1-1 前提知識 桁DP 解説 https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/count-zero-1-1/submissions/code/1318667751 難しいぞ。 ど…

Brackets Restoring [EEIC Programming Contest #0 D]

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/brackets-restoring 前提知識 カタラン数 解説 https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/brackets-restoring/submissions/code/1318663832 …

Barrier Protection [EEIC Programming Contest #0 A]

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/barrier-protection 前提知識 幾何の知識 解説 https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/barrier-protection/submissions/code/1318657703 …

Beautiful Rectangle [Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) C]

https://codeforces.com/contest/1276/problem/C 解説 https://codeforces.com/contest/1276/submission/66871784 説明と実装を簡単にするために、答えの長さをH≦Wとしておこう。 まず、自明なこととして、同じ種類の数はH個しか使えないことが分かる。 こっ…

Two Fairs [Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) B]

https://codeforces.com/contest/1276/problem/B 解説 https://codeforces.com/contest/1276/submission/66871631 あるx,yについて全ての経路でa,bを通るということは、 頂点a,bを抜くとxからyに到達不可能になるということ。 よって、頂点a,bを抜いた状態で…

As Simple as One and Two [Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) A]

https://codeforces.com/contest/1276/problem/A 解説 https://codeforces.com/contest/1276/submission/66871311 DPをして復元しよう。 dp[i][t] := i文字目まで処理が終わっていて状態がtのときの削除の最小値 状態のtは今までの文字列の末尾を指していて…

競技プログラミングにおける多項式問題まとめ [母関数、形式的べき級数、線形漸化式、高速きたまさ法]

多項式 数列の問題とか、組み合わせ問題を多項式の係数に置いて解くテクがある はまやんはまやん自信作の解説 testestestさんのまとまった資料 母関数・形式的べき級数 maspyさん資料1 maspyさん資料2 beetさん資料 latteさん資料 数列とかDPを母関数にして…

Sum Difference [AtCoder Beginner Contest 147 F]

https://atcoder.jp/contests/abc147/tasks/abc147_f 解説 https://atcoder.jp/contests/abc147/submissions/8936937 全体の総和は変わらないので、SかTのパターンを考えればよさそう。 Sのパターンを数えることにする。 組み合わせがちょっと多いので、何か…

Balanced Path [AtCoder Beginner Contest 147 E]

https://atcoder.jp/contests/abc147/tasks/abc147_e 前提知識 bitset 解説 https://atcoder.jp/contests/abc147/submissions/8904314 差の最小値を求めたい。 DPで「DP[y][x] := マス(x,y)までの経路での差の絶対値の最小値」みたいにしたいところだが、 そ…

Xor Sum 4 [AtCoder Beginner Contest 147 D]

https://atcoder.jp/contests/abc147/tasks/abc147_d 解説 https://atcoder.jp/contests/abc147/submissions/8892568 XORの計算は桁毎に考えることができる。 そのため、桁ごとに総和を求めて、その総和を取ることで答えとしよう。 こうすると、1がone個、0…

HonestOrUnkind2 [AtCoder Beginner Contest 147 C]

https://atcoder.jp/contests/abc147/tasks/abc147_c 解説 https://atcoder.jp/contests/abc147/submissions/8892526 この問題は競技プログラミング的な考え方が必要かもしれない。 競技プログラミングでは、最速のコードを出す必要はない。 制限時間に間に…

Palindrome-philia [AtCoder Beginner Contest 147 B]

https://atcoder.jp/contests/abc147/tasks/abc147_b 解説 https://atcoder.jp/contests/abc147/submissions/8892436 回文というのはある程度独立に考えることができる。 対応する位置について、文字があっているかどうか独立に考えていこう。 あっていなけ…

Blackjack [AtCoder Beginner Contest 147 A]

https://atcoder.jp/contests/abc147/tasks/abc147_a 解説 https://atcoder.jp/contests/abc147/submissions/8892419 与えられた数値の総和を求めて22以上か、未満かを判定しよう。 配列で回してもいいし、個別に取ってきても良い。 どっちが書くの早いだろ…

今年中に理解する!多項式、母関数、形式的べき級数の競プロでの実践的使い方

この記事はCompetitive Programming (1) Advent Calendar 2019の7日目の記事です。 対象読者 解説で多項式とか母関数とか形式的べき級数とか書いてあるとそっ閉じするあなた 厳密な話は要求しないから、テクニックとして理解したいあなた .oO(多項式の計算…

競技プログラミング 解説 RTA

この記事はCompetitive Programming (2) Advent Calendar 2019の7日目の記事です。 AtCoder Beginner Contest 146でこっそり一人解説RTAやってたので、動画とってた。 その各所での技術を以下は紹介する。 RTA動画はこれ ojt みんな大好きOnline Judge Tools…

Colorful Hats 2 [Sumitomo Mitsui Trust Bank Programming Contest 2019 E]

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8777300 着色をしていくわけだが、先頭から順番に色をつけていこう。 最初の0は3色のどれかが入る。次の0は残りの2色。最後は1…

Lucky PIN [Sumitomo Mitsui Trust Bank Programming Contest 2019 D]

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776950 3桁を指定するのはO(N3)かかってしまう。 だが、答えの組み合わせに注目してみると、103通りある。 これなら全探索でき…

100 to 105 [Sumitomo Mitsui Trust Bank Programming Contest 2019 C]

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c 前提知識 yes/no系動的計画法 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776665 品物は106個あるので、足りなくなることはない。 DPしよう。yes/noのDPをする。 dp[x] :=…

Tax Rate [Sumitomo Mitsui Trust Bank Programming Contest 2019 B]

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_b 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776597 N/1.08をすれば答えが得られそうではあるが、小数点以下切り捨てになっているので、ちょっとやりにくい。 Nの上限が500…