けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder500点

AtCoder ABC 213 F - Common Prefixes (黄色, 500 点)

これを機会に SA-IS を整備した! 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…

AtCoder ABC 213 E - Stronger Takahashi (水色, 500 点)

かの有名な「器物損壊!高橋君」の類題ですね。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。 今、左上のマス から右下のマス へと移動したいです。上下左右に移動することが…

AtCoder ABC 206 E - Divide Both (青色, 500 点)

約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1):約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…

AtCoder ABC 187 E - Through Path (水色, 500 点)

これの応用問題って感じだった!! drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…

AtCoder AGC 050 A - AtCoder Jumper (500 点)

これ本当にずっとわからなかった...言われてみればという感じ!! 問題へのリンク 問題概要 以下の条件を満たす、頂点数 の有向グラフ (頂点番号を とする) を構築せよ (自己ループも多重辺も可)。 すべての頂点の出次数は 2 である 任意の頂点対 に対して、…

AtCoder ABC 134 E - Sequence Decomposing (水色, 500 点)

実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…

AtCoder ABC 186 E - Throne (水色, 500 点)

一次合同方程式を解く問題です! 問題へのリンク 問題概要 円周上に 個の椅子が並べられています。そのうち 1 つは玉座です。 高橋君は最初、玉座から時計回りに数えて 個隣の椅子に座っており、次の行動を繰り返します。 行動:いま座っている椅子から時計…

AtCoder ABC 185 E - Sequence Matching (水色, 500 点)

LCS (Longest Common Subsequence) によく似た DP!! 問題へのリンク 問題概要 (意訳) 長さ の整数列 と、長さ の整数列 が与えられる。これらに以下の操作を繰り返すことで、要素数が等しくなるようにしたい。 A の要素を 1 つ選んで削除する B の要素を 1…

AtCoder ARC 110 C - Exoswap (緑色, 500 点)

「転倒数 = N-1 で Yes とする」という嘘解法が大量に通ったらしい 問題へのリンク 問題概要 の順列 が与えられる。 と を swap する と を swap する ... と を swap する という 種類の操作を、それぞれちょうど 1 回ずつ行う必要がある。その結果がソート…

AtCoder ARC 109 C - Large RPS Tournament (緑色, 500 点)

DP でやったけど、もっと楽にできたみたい 問題へのリンク 問題概要 長さ の文字列 と、正の整数 が与えられる。 人がジャンケンのトーナメント戦を行う。 は "R", "P", "S" のみからなる文字列で、"R" はグー、"P" はパー、"S" はチョキを表す。 (0-indexed…

AtCoder ARC 108 C - Keep Graph Connected (水色, 500 点)

誤読したーーーーー 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる (多重辺はありうるが、自己ループはない)。各辺には色がついていて、色は 以上 以下の整数値で与えられる。 各頂点に 以上 以下の色を割り振りたい。このとき、「…

AtCoder ABC 184 E - Third Avenue (水色, 500 点)

おおむね BFS だけど、ちょっとだけ TLE に注意。。。 問題へのリンク 問題概要 のグリッドが与えられる。"." は通路マス、"#" は壁で侵入不能マス、"S" はスタート、"G" はゴールである。さらに英小文字で表された各マス間は 1 手で自由にワープで行き来可…

AtCoder ABC 183 E - Queen on Grid (水色, 500 点)

三乗の解法はすぐに出てくるので、それを上手に高速化する! 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…

AtCoder ABC 170 E - Smart Infants (水色, 500 点)

こういうの苦手すぎるので、素早く綺麗に実装できるようになりたい 問題へのリンク 問題概要 AtCoder に参加している幼児が 人おり、 から の番号が付けられている。また、幼稚園 がある。幼児 のレートは であり、はじめ幼稚園 に所属している。 これから …

AtCoder ABC 181 E - Transformable Teacher (緑色, 500 点)

頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…

AtCoder ARC 107 C - Shuffle Permutation (水色, 500 点)

面白かった 問題へのリンク 問題概要 の行列 と、整数 が与えられる。この行列は、 をちょうど一つずつ要素に含む。 sigma くんは、以下の 2 種類の操作を、好きな順序で 好きな回数 行えます。 全ての について を満たす を選び、行列の 列目をswapする 全…

AtCoder ABC 177 E - Coprime (緑色, 500 点)

結構教育的!! 問題へのリンク 問題概要 個の正の整数 が与えられる。 これらのうちのどの 2 つも互いに素であるとき、"pairwise coprime" そうではなく 個の最大公約数が 1 であるとき、"setwise coprime それ以外のとき、"not coprime" と出力せよ。 制約…

AtCoder ABC 178 E - Dist Max (緑色, 500 点)

これ!!!!!HUPC 2019 day2 セットで出したやつや!!! 問題へのリンク 問題概要 二次元平面上に 個の点 がある。これらのうちの 2 点のマンハッタン距離として考えられる最大値を求めよ。 制約 考えたこと 2 点の位置関係としては、以下の 2 パターンが…

AtCoder ARC 106 C - Solutions (水色, 500 点)

面白かった 問題へのリンク 問題概要 以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。 はすべて互いに相異なる整数 これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君…

AtCoder ABC 180 E - Traveling Salesman among Aerial Cities (水色, 500 点)

TSP だ!! 問題へのリンク 問題概要 3 次元空間内に 個の都市、都市 1 から 都市 N がある。 座標 の都市から の都市に移動する際には のコストがかかる。 都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めよ。 制…

AtCoder ARC 105 C - Camels and Bridge (青色, 500 点)

難しかった 問題へのリンク 問題概要 体重が であるような 体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可…

HHKB プログラミングコンテスト 2020 E - Lamps (水色, 500 点)

これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。あるマスは壁 ('#') になっていて、あるマスは通路 ('.') になっている。通路マスが 個あるとして、すべての「通路マスの部分集合」 ( 通りある) に対して、以…

ACL Beginner Contest E - Replace Digits (青色, 500 点)

まさに遅延評価セグメント木の練習問題!!! 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…

AtCoder ABC 179 E - Sequence Sum (緑色, 500 点)

この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…

AtCoder ABC 175 E - Picking Goods (水色, 500 点)

最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった... 問題へのリンク 問題概要 二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。 K 個の座標 () に価値 のアイテムがある。通った…

AtCoder ABC 171 E - Red Scarf (茶色, 500 点)

XOR について完全理解することが求められる...! 問題へのリンク 問題概要 を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。 個の整数のうち 番目を除外した 個の整数の XOR 和が となる 制約 考えたこと が偶数というのが不気…

AtCoder ABC 169 E - Count Median (水色, 500 点)

未証明でも確信持てる系。でも、こういう風に「作れるものは連続している」というのはたまに見るパターン。そういう問題には「とりうる状態が連結」というタグをつけているので是非に!! drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 を次の…

AtCoder ABC 164 E - Two Currencies (青色, 500 点)

これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…

AtCoder ABC 163 E - Active Infants (黄色, 500 点)

探索順序を上手に決めると、普通の DP になる系!!! EDPC の Zubton なんかもそうやね! 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…