読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

Codeforces #361 (Div.2) D. Friends and Subsequences

問題 問題概要 [l, r]の区間を考えた時に, al, .. , ar の最大値と bl, .. , br の最小値が一致する区間の総数を求める. 解法 区間の左端を固定して, 右端を伸ばしていくと, aの最大値は単調増加, bの最小値は単調減少していくので, 区間を伸ばしていくとど…

Codeforces 400 (Div. 1 + Div. 2, combined) B. Sherlock and his girlfriend

問題 問題概要 i番目のものをi+1として考えて, 色を塗っていく. 塗る色はその数の素因数と同じ色にしてはいけない. 塗る色の最小数を求める問題. 解法 その数しか素因数を持たない素数はすべて同じ色で塗ることが可能. そのようにすると, 素数でない数はすべ…

Codeforece 400 (Div. 1 + Div. 2, combined) A. A Serial Killer

問題 問題概要 文字列が2つ与えられる. ひとつの文字列を指定された文字列に置換する操作を行うクエリに応える. 解法 setで管理しながら, 置換される方をeraseして, 加える方をinsertしていけばいい. ミス なし. コード #include <bits/stdc++.h> using namespace std; type</bits/stdc++.h>…

codeforces 401 div2 D. Cloud of Hashtags

問題 問題概要 与えられた文字列をすべて与えらた順番で辞書順にする. そのために各文字列から末尾の文字を好きなだけ取り除いていい. 取り除く文字の最小数を求める問題. 解法 一番後ろの文字はそのままにできることがわかるので, 後ろから順番に見ていき, …

codeforces 401 div2 B. Game of Credit Cards

問題 問題概要 数列a, bが与えられる. 数列bは好きな順番に変更することができる. (1) a[i] > b[i] となる i の個数の最小数 (2) a[i] < b[i]となる i の個数の最大数 を求める問題 解法 2部マッチングの最大数を使ってとく. 数列bを任意の順番に動かすこと…

codeforces 401 div2 A. Shell Game

問題 問題概要 カップを3つ用意して, その中のどこかに玉をいれる. カップの番号を左から0, 1, 2としてn回動かす. その動かし方は, 奇数回の時は0と1を入れ替えて, 偶数回の時は1と2を入れ替える. n回入れ替えたあとの位置が与えられるので, はじめ何番目の…

codeforces 225 div1 C. Propagating tree

問題 問題概要 (1)頂点vにxを加算し、その子に-xを加算し、またその子にxを加算する。 (2)頂点xの値を求める 解法 オイラーツアーで求めた順番で隣あうものは頂点の深さの差が1である。これを利用すれば、プラスマイナスの加算をsegtreeを2つ使って行うこと…

codeforces 368 div2 C. Pythagorean Triples

問題 問題概要 1辺の長さ与えられる。その辺を1辺とする、3辺が整数となる正三角形をを作れるなら、ほかの2辺の値をもとめよ。 解法 なんか数学的にあるんだろうなーと思ってググったら、ピタゴラス数の一般組があるみたい。 nが奇数のときと偶数のときで異…

codeforces 368 div2 B. Bakery

問題 問題概要 小麦屋さん以外の頂点でパン屋を開こうとする場合に、もっとも小麦屋さんから近くでパン屋を開ける頂点までの距離をもとめよ。開けないなら-1。 解法 ダイクストラで解いた。スタートをすべての小麦屋さんにして、それらの頂点からほかの頂点…

codeforces 374 div2 D. Maxim and Array

問題 問題概要 数列aが与えられる。この数列の積を最小に知るために、k回数列の数字を+xまたは、-xすることができる。どのように数列を変えるかを求めよ。 解法 重要な考察が、数列のすべての数字の積を大きくするには、一番小さい数字を大きくしていけばい…

codeforces 374 div2 C. Journey

問題 問題概要 有向グラフが与えられる。1からnまで距離T以下で行く中で、辿る頂点の数を最大にする経路を求める。 解法 dpの解法は、dp[i][j] := i個の名所を回って、j番目の名所にいるときの、移動時間の最小値 として更新していけば解くことができた。今…

codeforces 374 div2 B. Passwords

問題 問題概要 パスワードがいくつか与えれる。正解のpwも与えらる。パスワードを長さが短いものから順に試していく。このようにパスワードを試していったときに、最短なんか秒で答えのパスワードを入力することになるか、また、最大の場合も求める。ただし…

codeforces 374 div2 A. One-dimensional Japanese Crossword

問題 問題概要 連続する黒のマスの数。 解法 Bが始まった位置をl、Bが終わった位置をrを記録しながら、やる。 ミス サンプルから推測 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #def</cmath></cstdio></queue></vector></algorithm></iostream>…

Codeforces 364 Div2 C. They Are Everywhere

問題 問題概要 省略。 解法 しゃくとり法を使った。右を進めていき、条件を満たしたら、左を進めていく、最小の長さが出るようにしゃくとり法を使う。mapで全ての文字が、[l, r]に含まれているかを判定している。 ミス なし コード #include <iostream> #include <cstdio> #inc</cstdio></iostream>…

Codeforces 364 Div2 B. Cells Not Under Attack

問題 問題概要 省略。 解法 行、列、別々に、何個ずつ埋まっているかを見て、それを使い、計算すればいい。行、列が埋まるごとに、小さくなっていく。 ミス なし コード #include <iostream> #include <cstdio> #include <set> typedef long long ll; using namespace std; #define </set></cstdio></iostream>…

Codeforces 364 Div2 A. Cards

問題 問題概要 省略。 解法 数字をソートして、一番前と一番後ろから順にとっていく。 ミス なし コード #include <iostream> #include <algorithm> #include <cstdio> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int main(void){ int n; cin >> n; vector<pair<int, int> </pair<int,></vector></cstdio></algorithm></iostream>…

Codeforces Educational Codeforces Round 16 C. Magic Odd Square

問題 問題概要 nが与えられた時、1からn2まで使いn x nのますを縦横斜め全ての和が奇数になるように、埋めていく。 解法 縦横斜めの和が奇数になるのは、それらの一列に、奇数が奇数個ある時。この条件を満たすには、真ん中に十字形に奇数と配置し、4隅に階…

codeforces Educational Codeforces Round 16 B. Optimal Point on a Line

問題 問題概要 x座標上のnこの点が与えられる。それらの点の中から、他の点までの距離の合計が最小となるものを見つけろ。 解法 中央値は母集団の各要素から絶対距離の和が最も小さくするという意味で母集団を代表していると見ることができる(Wikipedia)とか…

Codeforces Educational Codeforces Round 16 A. King Moves

問題 問題概要 チェスのキングのコマの位置が与えられる。次の手で何通りの進み方があるか。 解法 キングは周囲8方向に1マスずつ進めるので、周りがマスに囲まれていれば、8通りの進み方がある。ただし、隅っこの場合などは変わる。8方向に動かして、範囲内…

Codeforces 363 Div2 B. One Bomb

問題 問題概要 縦横のマスが与えられる。その中に壁が含まれていて、それらを爆弾で吹き飛ばす。爆弾の効果は、爆弾を置いた列と行のすべての爆弾を吹き飛ばす。 解法 まず、列と行ごとに壁の数をメモしておく。これをしないで、毎回調べるとTLE。また、すべ…

Codeforces 363 Div2 A. Launch of Collider

問題 問題概要 粒子の数字(座標)とそれに対応するLRのどちらかが与えられる。Lの場合、その座標から左に動かすことができ、Rの場合、その座標から右に動かすことができる。粒子が1秒で1マス分、指定された 方向に動くことができる。最短何秒でぶつかるか。ま…