問題 https://atcoder.jp/contests/typical90/tasks/typical90_am 解説 kyopro_educational_90/039.jpg at main · E869120/kyopro_educational_90 · GitHub【問題】 重みのない木が与えられる。 任意の2頂点の最短パス長の総和を求めよ。 【典型ポイント】 …

https://atcoder.jp/contests/typical90/tasks/typical90_ah ベーシックなしゃくとり法【問題】 数列の区間のうち、含まれる値の種類がK種類以下である最長の連続部分列を求めよ。 【典型ポイント】 しゃくとり法 【方針】 見たまんま、しゃくとり法の典型問…

問題https://atcoder.jp/contests/typical90/tasks/typical90_aq 解説 https://twitter.com/e869120/status/1394787605099601923/photo/1 【問題】 二次元迷路のスタートからゴールへの経路のうち、最も曲がる回数が少ない経路の回数を求めよ 【典型ポイント…

atcoder.jp 桁DPの典型的な問題 【題意】 自然数の区間[A, B]において、4または9を含む整数はいくつあるか？ 【典型ポイント】 1~Nの数え上げは桁DP 区間和 【方針】 dp[i][smaller][j]:=1~Nの整数のうち、前方i桁まで見て、4または9が含まれている(j==1)か…

atcoder.jp 桁DPの典型的な問題【題意】 自然数の区間[A, B]において、4または9を含む整数はいくつあるか？ 【典型ポイント】 1~Nの数え上げは桁DP 区間和 【方針】 dp[i][smaller][j]:=1~Nの整数のうち、前方i桁まで見て、4または9が含まれている(j==1)か含…

atcoder.jp ゲーム系。 勝負が確定している後ろからDPする(バックトラックというらしい) この方針は正しかったが、7の倍数判定を無駄に考えすぎて解けず。【問題】 数列が与えられる。 文字列の手番に従って、高橋君と青木君は新しい数列の末尾にS[i]か0を加…

条件の厳しいやつからペアを組ませる系 atcoder.jp 【問題】 箱と荷物がある。荷物には重さと価値があり、箱は重さXi以下の荷物を1つしか入れられない。 適切に箱に荷物を詰めて価値を最大化せよ。 ただし、クエリごとに詰められない箱の区間が与えられる。 …

atcoder.jp ケーキをパラメータの合計値でグループ分けする、という考察までは進んだが、そこで詰まった。 【問題】 1各パラメータの昇順に並んでいる。K番目の(a,b,c)の値を出力せよ。 【典型ポイント】 辞書順Ｋ番目を求める問題は、各パラメータごとにグ…

排他的論理和(XOR)に関する問題 E - Xor Distances 木の重みを桁ごとに分解

本番で解けず。重みを桁ごとに分解するという発想がなかった 【問題】 重み付き木が与えられる。 dist(i, j) = iからjへの最短パスに含まれる辺すべての重みのXOR すべてのi ,j(i<j)についてdistの総和を求めよ 【忘れがちな知識】 総和は桁ごとに独立して足し合わせられる 例：123+789 = 1*10^2+7*10^2+2*10^1+8*10^1+3^10^0+9*10^0 【典型ポイント】 XOR => 桁ごとに考える 【方針】 愚直にdist(i,j)を全列挙としようとすると最低でもO</j)についてdistの総和を求めよ>…