atcoder-typical90

atcoder典型90問を日々解いていく

その過程で, 必要があればテンプレートを更新していく

問題の解法メモ

まずは★5以下のものを順番に解いていきます. その後, ★6, ★7にチャレンジします.

001: スコアを最大にする最適な切れ目を選択

答えでないかどうかの判定が高速にできる場合は, 答えで二分探索する

002: 括弧のあり得る場合を生成

小さい規模のものは全探索する

003: グラフが木である場合の最長距離

最短距離計算を2回行う

ある頂点から他の頂点への最短距離を求める
最も距離が長かった頂点を基準に, 他の頂点への最短距離を求める

004: 行列の各セルの縦横の和

何度も同じデータを参照する場合は, 事前計算しておく

事前計算で縦の和, 横の和を計算しておく

006: 最小部分文字列

貪欲に1文字ずつ決定していく

何度も同じデータを参照しないように, 各アルファベットがそれ以降でどのポジションにあるのか事前計算しておく

007: 最も近い要素の検索

ソートして挿入位置を二分探索で検索する

008: 部分文字列の場合の数

漸化式を立ててDPで解く

事前に関係ない文字は除外しておく
入力された文字列を後ろから参照していく
漸化式 (文字に対応する数字をa:0, t:1, c:2, o:3, d:4, e:5, r:6として, 後ろからi番目の文字がkに対応するとき)
- k=6のとき dp[k][i+1] = dp[k][i]+1
- k<6のとき dp[k][i+1] = dp[k+1][i]+dp[k][i];

010: 区間の和

累積和の差で解く

012: 塗られたマスの連結判定

UnionFindで解く

013: 経由地点のある最短経路

スタート地点からのダイクストラとゴール地点からのダイクストラで解く

014: 最も近くなるような人と学校の一対一対応

それぞれソートして差をとる

016: 最小のコイン枚数

無駄を省いた全探索をする

制約「合計9999枚以下の硬貨でちょうどN円を支払うことができる」も見逃さないようにする

018: 俯角を求める

逆三角関数を使って角度を求める

atan2(y, x)

020: log同士の数値の比較

桁数に注意してlong longで受け取り, logの中身を整数で比較する

021: 相互に行き来できる頂点のペア数

強連結成分分解を使って, 頂点をお互いに行き来できるグループに分ける

強連結成分分解のアルゴリズム:

DFSで頂点をたどり, 帰りに訪問したことにする (すべてたどれなければ訪問できなかった頂点からDFSを再開する)
辺の向きをすべて反転させ, 1.の訪問と逆順にDFSを行う (それぞれのDFSでたどれた分が強連結成分となる)

022: 直方体を立方体に分割するのに必要なカット数

3辺の最大公約数を求める

g = gcd(a, b, c) = gcd(gcd(a, b), c)
切る回数は (a/g - 1) + (b/g - 1) + (c/g - 1)

024: 2つの数列を一致させるための手数

ステップ数の偶奇性に注目する

2つの数列の差が与えられたステップ数Kより大きいなら一致不可能
差がK以下なら, +/-を交互に行うことで残りの手数を消費できる (偶数ならちょうど消費できる)

026: 隣り合わない頂点を取り出す

DFSで訪問順に交互に色を塗っていく

027: レコードが登録されているかの確認

集合を使うだけ

028: 複数の長方形の重なった面積

領域にすべての点をメモしておいて, 最後に累積和で重なっている数をセルに記録する (いもす法)

1001 x 1001の2次元配列aを用意
- 与えられる点の範囲が0から1000であることに注目
与えられた長方形の点(lx,ly), (rx,ry)に対して次のように記録
- a[lx][ly]++
- a[rx][ry]++
- a[lx][ry]--
- a[rx][ly]--
- 長方形領域ごとに毎回加算するとTLEになってしまうことに注意
行方向の累積和をaに記録後, 列方向に累積和をaに記録
- これで各セルに重なっている長方形の数が記載される

029: 区間の最大値の更新と取得

遅延評価付きのセグメント木で解く

030: N以下の素因数の数

エラトステネスのふるいで解く

032: 最小となる組み合わせを探索

空間が小さいため, 全探索する

全パターンを試すときにnext_permutationを使っても良い

033: ライトをつける位置

コーナーケース(例外)に気をつける

034: K種類以下の連続する最大部分列

単調性を利用して1長さを減らしたり増やしたりする (尺取り法というらしい)

036: 最大マンハッタン距離

点を45度回転させると考えやすい

037: 重さの範囲があるナップサック問題

DPで解くが, 最大値を求めるときにセグメント木を使う

038: 大きい数の最小公倍数

lcm(a, b) = a * b / gcd(a, b) オーバーフローに注意して, しきい値より大きいかの判定には除算を使う

039: 木のすべての頂点の組の最短距離の和

各辺を何回通る必要があるかを考える

深さ優先探索で各部分木に頂点がいくつあるかを調べる
それぞれの辺は頂点を2つの集合に分けるため, 1で求めた頂点の数からその辺を通る回数を求める

042: 各桁の和がKになる9の倍数の数

「9の倍数 = 各桁の和が9の倍数」という性質を使う. Kが9の倍数でなければゼロ, Kが9の倍数なら各桁の和がKとなる数をDPで求める

043: 迷路でゴールするまでの曲がる回数の最小値

dequeを使った01BFSで, コストが小さいところからたどっていく

位置だけでなく, たどってきた向きも記録しておく
迷路の周りを壁で囲んでおくと, はみ出るかどうかの処理が楽になる
priority_queueを使ったダイクストラでもOKだが計算コストは少し増える

044: 配列のシフトを頻繁に行う問題

シフトした数を覚えておいて, 実際にはシフトしない

046: 3つの数列からそれぞれ1つずつ選んだ整数の和が46の倍数になる総数

mod 46で考えて, それぞれの数列で個数をカウントして, 全探索(46^3)する

048: 試験の時間配分最適化

1分かけて部分点bがとれて, さらに1分かけると(満点a-部分点b)(<a/2)がとれることを利用して, ソートして上位k個を選ぶ

050: 階段を登る総数

漸化式を立ててDPで解く

051: 合計P円以下でN個の商品からちょうどK個選ぶときの総数

全探索2^40ではTLEになるので, 商品集合を半分に分けてそれぞれ全探索2^20した2つの結果を統合する

それぞれの商品集合で, 個数ごとに価格リストを昇順に持っておく
結果の統合には, 片方の集合の価格から見て, もう一方の集合の価格リストを二分探索して個数を求める

052: 複数のサイコロを振ったときの目の積の総和

式をかいてsumの位置を移動させる

たとえば3つのサイコロなら, sum{i0}sum{i1}sum{i2}A[0,i0]A[1,i1]A[2,i2] = sum{i0}A[0,i0]sum{i1}A[1,i1]sum{i2}A[2,i2]

055: 整数から5つ選んだ積をPで割った余りがQである総数

全探索する. 積がオーバーフローしないように適宜mod pで考える.

056: N日間にわたり各2つの商品を選んで合計S円になるか判定し, そのプロセスを出力

DPでS円になるか判定し, DPテーブルを逆順にたどって解を求める

058: ある操作によって10^5未満の値の推移を10^18回行う問題

周期性を検出して省略する

060: 与えられた数列で途中まで増加して途中から減少する部分数列の最大長

最長増加部分列を左右から利用する

061: 山札にカードを一番上, 一番下に追加できて, 任意の位置のカードを取得する

長い配列を用意して中央から埋めていくようにする

c++のdequeはランダムアクセスがO(1)でできるらしいので, dequeを使っても良い

063: 行列から任意の個数の行と列を選択して, すべて同じ値になるときの最大サイズ

行が8行以下という制約から, 行の選択に関して全探索して, 同じ値のみがある列から最も多い値のものを選ぶ

064: ある添字の範囲で同じ値だけ数値が変動する場合の数列の隣同士要素の差の絶対値の和

差分だけを考えると, 更新する箇所は各クエリに対して2箇所のみ

たとえば, |a-b|+|b-c|+|c-d|+|d-e|とあって, b,c,dに+vすると|a-b-v|+|b+v-c-v|+|c+v-d-v|+|d+v-e|=|a-b-v|+|b-c|+|c-d|+|d-e+v|

066: 数列に範囲が与えられた場合の転倒数の期待値

期待値の線形性(和の期待値は期待値の和)を使って, それぞれの2つの期待値の和を計算する

067: 8進数を9進数に直す

8進数から10進数に直し, 10進数を9進数に変換する

長さLの8進数文字列S → 10進数 N
- N = sum_i S[L-i-1] * 8^i
10進数 N → 9進数文字列S
- N!=0の間繰り返す
  - S = "N%9" + S
  - N/=9

068: クエリによってだんだん情報が与えられていく問題

クエリを先読みして, 辺をつなげておく
未確定な値をゼロで仮に埋めておいてすべての値を確定させておくｰ実際に値が与えられたら, その差分を計算し, ノードが奇数個離れているか偶数個離れているかで値の差を足すか引くか決める
その時点で与えられている情報で値が確定できるかどうかは, 連結判定を別で持っておく
連結判定はUnionFindかsetのlower_boundを使うと可能
- s.lower_bound(x)を使わず, lower_bound(s.begin(), s.end(), x)にするとTLEになるため注意

069: 2つ隣まで異なる色で塗り分けるときの場合の数

高速べき乗法を使う

070: すべての点からのマンハッタン距離の和の最小値

x軸, y軸それぞれ独立に考えて, 中央値を求める

差の絶対値が最小になる点は中央値

072: 小さなマップ上で移動して戻ってこれる経路の最大長

マップが小さいので再帰関数で全探索する

実装上楽になる工夫: マップの周りを壁で囲むことでindexがはみ出るかの判定を省ける

073: 木において, 連結成分がラベルを2種類含む場合の数

DFSで木DPで解く

dp[now][連結成分のラベル集合]=部分木で条件を満たすものが何通りか
nowのラベルがaのとき {a} を生成するのは
- 辺(now, child)を削除する場合, 部分木が条件を満たすために dp[child][{a,b}]
- 辺(now, child)を削除しない場合, {a}だけにならないといけないため dp[child][{a}]
- すべての子でこれらのパターンがあるため, dp[now][{a}] = prod(dp[child][{a}] + dp[child][{a,b}])
nowのラベルがaのとき {a,b} を生成するのは
- dp[now][{a,b}] = すべての場合 - dp[now][{a}]
- すべての場合 = prod(dp[child][{a}]+dp[child][{b}]+2*dp[child][{a,b}])
- ※ dp[child][{a,b}]は辺(now, child)を削除する場合も含むため係数2がつく

075: 整数を2つの積に分解する操作を最小何回行えばすべての数字が素数になるかの

素因数分解を行い, log2(素因数の数)回行えば良いとわかる

076: 切れ目の入ったケーキのうち, 連続した取り出し方でちょうど全体の10分の1の塊を取り出せれるか

円形を回避するために2回配列を並べて累積和をとり, それぞれのピース位置から始めたときに終了時点を2分探索する

078: 隣接頂点番号が自分自身より小さい頂点数がちょうど1の頂点数

与えられた辺を順に見ていき, 頂点ごとにカウントするだけ

079: 2x2ブロックを±1できるときに2つの行列を一致させる手数

左上から順番に処理していく

081: 身長と体重のそれぞれの差がK以下となる人数の最大値

身長体重を二次元配列上の点としてカウントし, K x Kの長方形領域を全探索でずらしていく

長方形領域内の和は, 行方向の累積和, 列方向の累積和の順で事前計算をしておくと, 以下の値が長方形領域内の和になる
- cumsum[i+k][j+k]-cumsum[i-1][j+k]-cumsum[i+k][j-1]+cumsum[i-1][j-1]

082: LからRまでの整数xをx回連ねて書いたときの桁数

桁数ごとに, 書きこむ回数を求める

等差数列の和
- 1 + 2 + ... + N = N(N+1)/2
- L + ... + R = n(L+R)/2
  - 項数: n = R-L+1
aのmod pにおける逆元
- a^(p-2) mod p
  - p: 素数
  - フェルマーの小定理から a * a^(p-2) = 1 (mod p)
unsigned long long (ULL)
- ULLの最大値は18446744073709551615 (20桁)
- LLの最大値は9223372036854775807 (19桁)
- オーバーフロー対策としてULLを使うか, 2で割る際に場合分けが必要

084: 2種類の文字を含む区間の数

i文字目以降にどの位置に別の文字が出るかを記録しておくことで計算可能

もしくは, 余事象を考えて2種類の文字を含まない総数を数えてもよい

085: abc=Kを満たす正の整数の数

約数列挙して全探索する

オーバーフローに注意

086: ビットで指定された条件を満たす数列のパターン数

ビットごとにbit全探索をする

i桁目を取り出す: (A>>i)&1

087: 指定されたいくつかの頂点間の距離をXと決めたときに, 一定距離以下で到達可能な組数がちょうどK個になるときのXの総数

全頂点間の距離を求め, 答えXで二分探索する

全頂点間の距離: Floyd–Warshallで求める
- dijkstraで1対他をN回やってもよい
二分探索: lower_boundとupper_boundを求める
- Xが上昇すると到達可能なペア数が減るため, 広義単調減少
- lower_boundとupper_boundの差が答えになる

Name		Name	Last commit message	Last commit date
Latest commit History 62 Commits
.gitignore		.gitignore
001.cpp		001.cpp
002.cpp		002.cpp
003.cpp		003.cpp
004.cpp		004.cpp
006.cpp		006.cpp
007.cpp		007.cpp
008.cpp		008.cpp
010.cpp		010.cpp
012.cpp		012.cpp
013.cpp		013.cpp
014.cpp		014.cpp
016.cpp		016.cpp
018.cpp		018.cpp
020.cpp		020.cpp
021.cpp		021.cpp
022.cpp		022.cpp
024.cpp		024.cpp
026.cpp		026.cpp
027.cpp		027.cpp
028.cpp		028.cpp
029.cpp		029.cpp
030.cpp		030.cpp
032.cpp		032.cpp
033.cpp		033.cpp
034.cpp		034.cpp
036.cpp		036.cpp
037.cpp		037.cpp
038.cpp		038.cpp
039.cpp		039.cpp
042.cpp		042.cpp
043.cpp		043.cpp
044.cpp		044.cpp
046.cpp		046.cpp
048.cpp		048.cpp
050.cpp		050.cpp
051.cpp		051.cpp
052.cpp		052.cpp
055.cpp		055.cpp
056.cpp		056.cpp
058.cpp		058.cpp
060.cpp		060.cpp
061.cpp		061.cpp
063.cpp		063.cpp
064.cpp		064.cpp
066.cpp		066.cpp
067.cpp		067.cpp
068.cpp		068.cpp
069.cpp		069.cpp
070.cpp		070.cpp
072.cpp		072.cpp
073.cpp		073.cpp
075.cpp		075.cpp
076.cpp		076.cpp
078.cpp		078.cpp
079.cpp		079.cpp
081.cpp		081.cpp
082.cpp		082.cpp
084.cpp		084.cpp
085.cpp		085.cpp
086.cpp		086.cpp
087.cpp		087.cpp
Makefile		Makefile
README.md		README.md

birdwatcherYT/atcoder-typical90

Folders and files

Latest commit

History

Repository files navigation