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

hamayanhamayan's blog

競技プログラミング

Extension [AtCoder Grand Contest 046 B]

https://atcoder.jp/contests/agc046/tasks/agc046_b 解説 https://atcoder.jp/contests/agc046/submissions/14512309 まずはDPから考えてみる とりあえずmod数え上げなので、DPから考えてみる。 制約からまず以下のDPをベースに考え始めてみる。 dp[h][w] :…

Takahashikun, The Strider [AtCoder Grand Contest 046 A]

https://atcoder.jp/contests/agc046/tasks/agc046_a 解説 https://atcoder.jp/contests/agc046/submissions/14511770 まず自明な所から考えてみると、 X=180, X=90, X=60みたいな正多角形で内角が整数であるものは360/Xが答えになっている。 X=100のような…

桁和の桁和2 [yukicoder 1086]

https://yukicoder.me/problems/no/1086 解説 https://yukicoder.me/submissions/500440 下位問題があるので、そちらがまだならそちらを解いてから、こちらを考えるといい。 基本的には、下位問題と似たような感じになる。 数列の要素を数字根を計算して、そ…

桁和の桁和 [yukicoder 1085]

https://yukicoder.me/problems/no/1085 前提知識 数字根(知っていれば早い) 動的計画法 解説 https://yukicoder.me/submissions/500381 数字根を知らないとかなり時間をロスすると思う。 ある数について桁和を取れるだけとった結果を数字根という。 数字…

積の積 [yukicoder 1084]

https://yukicoder.me/problems/no/1084 前提知識 区間積セグメントツリー(または、スパーステーブル) 二分探索 一次(関数)imos 解説 https://yukicoder.me/submissions/500368 複合的な知識が必要。 まずは、全探索対象が区間となっているが、区間の全探…

余りの余り [yukicoder 1083]

https://yukicoder.me/problems/no/1083 解説 https://yukicoder.me/submissions/499917 見た目に難しい問題。 Nの制約が異常に小さいので、O(N2N)かな…といういつものやつを頭の片隅に置きつつ考える。 配列Aを固定した場合を考えてみよう。 modを取るとき…

XORのXOR [yukicoder 1082]

https://yukicoder.me/problems/no/1082 解説 https://yukicoder.me/submissions/499879 配列Aが固定されている場面でまずは考えてみよう。 すると、 Xは B1 xor B2 xor B3 xor ... xor BN-1 (A1 xor A2) xor (A2 xor A3) xor (A3 xor A4) xor ... xor (AN-1…

和の和 [yukicoder 1081]

https://yukicoder.me/problems/no/1081 解説 https://yukicoder.me/submissions/499832 シミュレーションをしていこう。 具体的には、A[i] += A[i + 1]を全部の要素に行うことをN - 1回やればいい。 すると、A[0]が答えになる。 もっと賢くやることもできそ…

Pond Skater [AtCoder Beginner Contest 170 F]

https://atcoder.jp/contests/abc170/tasks/abc170_f 解説 https://atcoder.jp/contests/abc170/submissions/14369162 後追いで解いて、色々な解法を目にしてしまったので、以下にまとめておく。 3種類見かけた。 難易度はどれもどれという感じもしているの…

Smart Infants [AtCoder Beginner Contest 170 E]

https://atcoder.jp/contests/abc170/tasks/abc170_e 前提知識 multiset 区間minセグメントツリー 解説 https://atcoder.jp/contests/abc170/submissions/14365126 シミュレーション高速化の問題。 データ構造をうまく使ってシミュレーションを高速化しよう…

Not Divisible [AtCoder Beginner Contest 170 D]

https://atcoder.jp/contests/abc170/tasks/abc170_d 前提知識 調和級数的計算量 解説 https://atcoder.jp/contests/abc170/submissions/14362889 この問題は調和級数的計算量を知らないと難しいかもしれない。 つまるところ、 「rep(i,1,N) for(j=i;j<=N;j+…

Forbidden List [AtCoder Beginner Contest 170 C]

https://atcoder.jp/contests/abc170/tasks/abc170_c 解説 https://atcoder.jp/contests/abc170/submissions/14358523 全探索で解く。 答えの候補は、制約を見ると[0,101]の範囲にしかない。 よって、答えを全探索して、数列pに含まれなくて、Xに最も近いも…

Crane and Turtle [AtCoder Beginner Contest 170 B]

https://atcoder.jp/contests/abc170/tasks/abc170_b 解説 https://atcoder.jp/contests/abc170/submissions/14354926 鶴亀算が与えられて、答えが存在するか判定する問題。 真面目に鶴亀算を解いてもいいのだが、計算機に頼るとしよう。 つまりは全探索する…

Five Variables [AtCoder Beginner Contest 170 A]

https://atcoder.jp/contests/abc170/tasks/abc170_a 解説 https://atcoder.jp/contests/abc170/submissions/14353028 0が何番目にあるかが分かればそれを答える。 受け取る変数は長さ5の配列に入れていくとループで見れて便利。 x[i]=0となるものを答えれば…

Knapsack Queries on a tree [東京海上日動 プログラミングコンテスト2020 D]

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_d 前提知識 半分全列挙 解説 https://atcoder.jp/contests/tokiomarine2020/submissions/14260465 だいぶ難しい問題。 ナップサックを半分全列挙で解く解法があるが、それを見たことない…

Lamps [東京海上日動 プログラミングコンテスト2020 C]

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_c 前提知識 imos法 解説 https://atcoder.jp/contests/tokiomarine2020/submissions/14259573 K回操作を行うとあるが、実験してみると、数が早いスピードで大きくなっていくことが分かる…

Tag [東京海上日動 プログラミングコンテスト2020 B]

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_b 解説 https://atcoder.jp/contests/tokiomarine2020/submissions/14258873 シミュレーションしていけばいい。 鬼は子供に常に向かうように移動すればいいし、子供は鬼から逃げるように…

Nickname [東京海上日動 プログラミングコンテスト2020 A]

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_a 解説 https://atcoder.jp/contests/tokiomarine2020/submissions/14258289 与えられた文字列から3文字選んで答えると答えになる。 どこから取っても問題ないので、最初から3文字を選ん…

Swap and Sort [第三回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202005-open/tasks/past202005_n 解説 https://atcoder.jp/contests/past202005-open/submissions/14080549 tsutajさんの解法, 公式解説にとてもエレガントな説明が書いてある。 久々に目が覚めるような経験をした。なるほ…

輪投げ [第三回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202005-open/tasks/past202005_o 前提知識 最小費用流 解説 https://atcoder.jp/contests/past202005-open/submissions/14070327 問題を見ると色々な制約がある。 各ラウンド事に命中させると点数を得ることができ、かつ、…

行商計画問題 [第三回 アルゴリズム実技検定 M]

https://atcoder.jp/contests/past202005-open/tasks/past202005_m 前提知識 ダイクストラ bitDP 解説 https://atcoder.jp/contests/past202005-open/submissions/14069459 制約でK≦16というのがあるので、戦略的にここから取り組む。 bitDPだろうと仮定が立…

スーパーマーケット [第三回 アルゴリズム実技検定 L]

https://atcoder.jp/contests/past202005-open/tasks/past202005_l 解説 https://atcoder.jp/contests/past202005-open/submissions/14069260 この問題の制約で1≦ai≦2というどう見てもおかしい制約があるので、ここから考える。 ai=1かai=2の2パターンしかな…

コンテナの移動 [第三回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202005-open/tasks/past202005_k 前提知識 単方向リスト 解説 https://atcoder.jp/contests/past202005-open/submissions/14068861 単方向リストを実装させる問題である。 (あまり見ないが、双方向リストであればコドフォ…

回転寿司 [第三回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202005-open/tasks/past202005_j 前提知識 セグメントツリー 二分探索 解説 https://atcoder.jp/contests/past202005-open/submissions/14068492 最初に「まだお寿司を1つを食べていない」という条件は、 自分の過去最高美…

行列操作 [第三回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202005-open/tasks/past202005_i 解説 https://atcoder.jp/contests/past202005-open/submissions/14068050 難しい問題。 差分を計算するイメージではあるが、情報をいかに圧縮して計算量を減らせるかという問題。 「4 A B…

ハードル走 [第三回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202005-open/tasks/past202005_h 前提知識 DP 解説 https://atcoder.jp/contests/past202005-open/submissions/14067495 DPで解く。 なんでDPって分かるんだ!という話であるが、 - N≦105で最小値、DPかな? - 行動によって…

グリッド金移動 [第三回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202005-open/tasks/past202005_g 前提知識 BFS 解説 https://atcoder.jp/contests/past202005-open/submissions/14067221 さあ、この辺からギアが上がってくる感じがある。 コスト1の移動である地点からある地点への最短距…

回文行列 [第三回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202005-open/tasks/past202005_f 解説 https://atcoder.jp/contests/past202005-open/submissions/14067015 たぶん、競技プログラミングをやってこないと回文を扱うプログラムを書いたことは無いだろうと思う。 まあそれは…

スプリンクラー [第三回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202005-open/tasks/past202005_e 解説 https://atcoder.jp/contests/past202005-open/submissions/14066764 この問題では、競技プログラミングではよく出る無向グラフをうまく扱えるかが問われている問題。 競プロでは、無…

電光掲示板 [第三回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202005-open/tasks/past202005_d 解説 https://atcoder.jp/contests/past202005-open/submissions/14066582 パターンマッチングを頑張る問題。 パターンマッチングなので、数と対応した文字列を紐づける必要があるが、 丁度…