ABC188

■A - Three-Point Shot
if (min(x, y) + 3 > max(x, y))


■B - Orthogonality
書いてあるとおりに計算


■C - ABC Tournament
前半の選手の最大と、後半の選手の最大を抽出し
決勝を行う。負けたほうが答え


■D - Snuke Prime
素直にやるとTLEするので
座標圧縮+imos


■E - Peddler
問題を読み違えて大事故
西の街から順番にdpっぽい感じで


■F - +1-1x2
AGC44 A - Pay to Win
下を有限にするために/2,+1,-1にしてゴールからスタートに向かうように読み替える
+1 -1は最後は連続して操作する必要がないことを考慮して
遷移は偶数なら/2 奇数なら+1して/2 or -1して/2でbfs

PAST5

■A - ○✕ゲーム
ジャッジが2^5ケースあってウケる
前から3文字セットで見てくだけ


■B - 上書き
それより後ろに同じ文字があれば採用しない
なければ採用するに読み替える。


■C - 三十六進法
N%36;
N/=36;で下から構築
0==inputがコーナーケース?


■D - リーディングゼロ
そのままだとstd::sortに打ち込んでも意味がないので
sort関数を自作する
文字列長が同じにしてなら比較するために
11と0012なら0011と0012にして比較
11と0011は0011と0011の比較になるが、その場合は0011が優先されるように


■E - ハンコ
90度回転させて4試す
SはsetでTはvectorで#の位置を保持しておく
90度回転後は-2 * max(H,W)から2 * max(H,W)までずらせばいいので
ずらした後のT#がS#と一致したらNG
ずらした後のT#がH*Wの範囲外ならNG
としてO(max(H,W)^2 * H * W)で可能


■F - 一触即発
問題文がわかりにくない?
bit全探索でO(2^N * N * M)
解説を見たらO(2^N * M)に落ちると書いてた


■G - ヘビ
dfs
制約が小さいといっても16!は無理ですが
全探索しても16*3^16にもならないので終わります


■H - コンベア
bfs
pastはとりあえずbfsとdfsがかければ中級まではいけます
全頂点からやるのは無理なのでゴールからたどってそこに行けるかどうか


■I - 避難計画
Hに続いてbfs
避難所起点でbfs


■J - 長い長い文字列
指されている文字はどこから来たものなのかを考える
後ろから見ていって状態を戻していくといつか最初に足されたタイミングにぶつかるのでそこが答え


■K - 的あて
tdpcのjがほぼ同じ問題


■L - T消し
tdpcのiがほぼ同じ問題


■M - 棒の出荷
二分探索


■N - 旅行会社
セグ木上での二分探索
これはaclに備わっているので貼るだけ


■O - 通知
やるだけと思ってやるとTLEしてしまうので
O(QN)やO(QM)をO(Q*sqrt(N or M))程度に落としたい
なので友達の数が多い少ない(sqrt(M)以上or未満)で処理を変えると良い

 

■感想
M,Nがわりかし簡単な割にK,LのDPが初見だと少し厳しそうに見える。
傾向としてdfs,bfs,dpが適切にかければ上級(Lまで)
後ろ3つのどれか2つが解ければエキスパート。

 

 

ARC(keyence2021)

■A - Two Sequences 2
maxAをA[0]からA[i-1]の最大値として
C[i] = max(C[i - 1],maxA * B[i])

 

■B - Mex Boxes
小さい数字から振り分けていくだけ

 

■C - Robot on Grid
dp[i][j][k]:=マス(i,j)にここまでk個記入済みマスを通ってきた場合の数だと間に合わない
dp[0][0]=3^(H*W-K)として遷移を*1と*0と*2/3に分類

 

■D - Choosing Up Sides
アダマール行列という知識があれば秒殺できるらしい

知らなくても再帰的に考えれば構築できるが、厳しい

実験→再帰はテクニックとして持っておきたい

 

■E - Greedy Ant

高度に行動する必要がないのですぬけはひつようなときにまとめて行動すればよい

dp[l][r][k]:=[l,r)が取られていてすぬけがk手使える

としてdfs

dfs(l,r,k)から

すぬけが行動:=dfs(l-1,r,k-1)とdfs(l,r+1,k-1)に遷移

蟻さんが行動:=dfs(l-1,r,k+1)とdfs(l,r+1,k+1)に遷移


■F - Keyence Repetition
未読

ARC111

■A - Simple Math 2
10 ^ N = a * M ^ 2 + b * M + cとすれば
bが答えになる
10 ^M * 10^N =(a0 * M ^ 2 + b0 * M + c0)*(a1 * M ^ 2 + b1 * M + c1)
なので新しくできるb cをb2 c2として
b2 = (b0 * c1 + b1 * c0 + (c0 * c1) % M )%M
c2 = c0 * c1 / M
なので繰り返し二乗法


■B - Reversible Cards
グラフに読み替え。
木か、そうじゃない(閉路を持つか)かをunionfindで判定
木なら頂点数 - 1 そうじゃないなら頂点数


■C - Too Heavy
初期状態で正しくない荷物を持ってお疲れじゃなければ可能なのは明らか。
重い荷物から順番に正しい持ち主に与えていけばOK。


■D - Orientation
C[i]とC[j]が異なるときは矢印が決まる
そうじゃないときはedgeを結んでおいて、根っこから順番に葉に向かって適当にやればそれが答え


■E - Simple Math 3

floor_sumやるだけ先に見とけばよかったね

 

■F - Do you like query problems?

 

abc187

■A - Large Digits
桁和の比較x%10とx/=10

■B - Gentle Pairs
dx = abs(xi-xj)
dy = abs(yi-yj)の比較
0 == dxは駄目

■C - 1-SAT
std::setに詰めていく
!aaの場合はaaがすでにあるか
aaの場合は!aaがすでにあるか

■D - Choose Me
演説を行わないとΣ-Ai票差でまける
演説をすると2*Ai+Bi票差が縮まるので
ソートして差が正になるまでやる

■E - Through Path
グラフなので説明が書けない
某フレンズさんのツイート参照

■F - Close Group
EDPCに例題あり
最初に2^n通りに対して完全グラフ化を調べておくO(2^N*N^2)
状態SからSの部分集合TとS/Tでdp[S]= max(dp[T]+dp[S/T])
計算量はn個ビットが立っている状態から2^n通りに遷移するので
NCn*2^n = (1+2)^N = 3^N

AGC050 AGC051

参加権がないのでJOIの虚無埋めしてました

■A - AtCoder Jumper
セグメント木とかであるやつ
1→2,3
2→4,5
3→6,7な感じで生やすとスタートが1のときはOK
Nを超えたらx%Nに飛ばすようにすれば
スタート1の木が無限に広がるので、どこをスタートとして見ても
10手先に連番で全ページが並ぶのでこれで問題なし

■B - Three Coins
区間DP
......を
.と.....
..と....
...と...
....と..
......と.
に分けて考えてそれぞれ和のmaxが答え
また区間幅が3の倍数なら
......はooooooに
ooooooは......に変化できるので
それもdpに組み込む


■A - Dodecagon
外から決めていく
三角形を使った辺の長さが減ることがサンプルと考察からわかるので
(1,1)→(1,0)みたいに変化していくことから
c(2*D,D)になることがわかる。
初手は固定できるのでその半分
つまりc(2*D-1,D)でも良い

■B - Bowling
初手次第な感じ
xxxxxxooo
xxxxxxxxx
xxxxxxxxx
xxxoooxxx
xxxxxxxxx
xxxxxxxxx
oooxxxxxx
A:3
B:3
C:9
D:9
となる
これをさらに3セット都合の良いように置くと
A:3*3
B:3*3
C:9*1
D:9*3
となるのでできそうな気がする
これを3から10に拡張すればOK

どちらも一時間でAB解ければ2300前後のパフォーマンス。
大変ですね。。

past4

■A - 中央値
やるだけ

■B - 電卓
printf("%.2f\n", ans);でWA
仕方ないので100倍

■C - 隣接カウント
const int dx = { -1,0,1,0,1,-1,1,-1,0 };
const int dy
= { 0,-1,0,1,1,-1,-1,1,0 };
としておくと楽

■D - 分身
両端から絶対に必要な分を決めて、
それ以外の幅を塗りつぶせるように調整

■E - アナグラム
next_permutation

■F - 構文解析
mapにいれてpairに持ち替えてsortして前後比較

■G - 村整備
壁の数だけBFS

■H - マス目のカット
二次元DPとか考えてみるけど
O(N*M*min(N, M)^3)が余裕で間に合うので愚直

■I - ピザ
尺取法
X>Yにして問題ないので
食べれるところまで食べる!

■J - ワープ
ワープは一回使ったら使用禁止としてbfsする

■K - 転倒数
それぞれの組に対して転倒数とどの数が何個持っているかを保持しておけばいい
1000000000で割ったあまりであることを忘れずに

■L - マンションの改築
遅延セグ木2本生やしてやるだけ。と思ったらガッツリTLE
共通で変化する差分と、単独で変化する差分を別に扱うといい

■M - 筆塗り
lca+unionfind
後ろのクエリから処理していく。
lacとuがsameになるまで登っていく
uのnextとlcaがsameなら何もせずに次に
そうじゃないならマージして次に
マージするついでにAnsをメモる

■N - マス目の穴埋め
dp
i行目とi+1行目の状態数2^12通りを持っておいて
その下にi+2をi+1行目と矛盾を発生させずに置けるかどうか。

■O - 宝箱
ダイクストラ
鍵屋を追加して辺を作成、遡るコスト0の辺の作成
どこかで類題を見た記憶