7K12 blog

猫でも分かる何か

2020-05-01から1ヶ月間の記事一覧

ABC145 E - All-you-can-eat

https://atcoder.jp/contests/abc145/submissions/12428154 商品を1個だけ手に持てるナップサックは通常DPと逆順DPを組み合わせると暗記 繰り返しは rep(i, 1, Size(nyaa)-1) rep(t, 0, T) 出力は ans = max(ans, dp1[i - 1][t] + dp2[i + 1][T - 1 - t] + n…

東京工業大学プログラミングコンテスト2019 C - XOR Filling

https://atcoder.jp/contests/ttpc2019/submissions/13679593 xor 演算は移項できる A xor B = X ⇔ B = X xor A 「xor 演算は(ビットサイズが同じなら)X以上のB → X以下の値2個 に分解できる」と暗記する つまり B = X xor B' (X < B, B' < X) が構築でき…

ABC144 E - Gluttony

https://atcoder.jp/contests/abc144/submissions/13628299 答え(が条件を満たすかどうか)で二分探索をする Kが無ければ簡単でAの昇順とFの降順を掛け算するのが最善になる。Kがある場合は値の大きいAを優先して減らせば良いが、求めたい最小値以上に減ら…

Kyoto University Programming Contest 2019 C - てんびんばかり

https://atcoder.jp/contests/kupc2019/submissions/13635953 K=1のときは有名で以下が答えになる 天秤の片方にしか分銅を載せられないなら 天秤の左右に載せられるなら K=1のときは有名で「バシェの分銅問題」という名前が付いているらしい。 ただし、今回…

ABC143 E - Travel by Car

https://atcoder.jp/contests/abc143/submissions/12257779 ワーシャルフロイド法を使ってショートカットを追加 補給回数の新しいグラフを作る 任意の頂点で燃料を満タンにリセットするため、単純な最短距離が最善とはならない。ワーシャルフロイド法を使う…

Kyoto University Programming Contest 2019 B - ナップサック問題

https://atcoder.jp/contests/kupc2019/submissions/13604182 初期値は dp[0]=0 繰り返しは rep(i, 1, Size(newItem)) rep(j, 0, n * Pow10(4) + 1) 更新は if (0 <= j - newItem[i].first) dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - newItem…

ABC142 E - Get Everything

https://atcoder.jp/contests/abc142/submissions/11902212 初期値はdp[0]=0 繰り返しは rep(i, 0, M) rep(j, 0, Pow2(N)) 遷移は dp[next] = min(dp[next], dp[j] + key[i].a); 出力は dp[Pow2(N) - 1]; 制約からbitDPと分かる。 各鍵key[i]と宝箱の空き状…

EDPC S - Digit Sum

https://atcoder.jp/contests/dp/submissions/11937787 初期値は rep(j, 0, 10) if (j == CtoL(K[0])) dp[0][j % D][stEQ] += 1; など K以下の整数全てとmod(D)全てで繰り返しは rep(i, 0, Size(K)) rep(j, 0, 10) rep(k, 0, D) 状態は state::LT (less than…

ABC141 E - Who Says a Pun?

https://atcoder.jp/contests/abc141/submissions/11639951 ZアルゴリズムはS[i]からの部分列と先頭からの部分列の最大一致文字数を返す Zアルゴリズムの計算量は ZアルゴリズムはS[i]からの部分文字列が先頭S[0]からの文字列と何文字一致するかで返す。した…

ABC168に参加した感想

A3分、B2分、C14分、D21分、の4完でした。初めてパフォ1200超えました。 A - ∴ (Therefore) https://atcoder.jp/contests/abc168/submissions/13300576 頑張ってタイピングします B - ... (Triple Dots) https://atcoder.jp/contests/abc168/submissions/132…

ABC139 E - League

https://atcoder.jp/contests/abc139/submissions/11590159 これでdif12Kとかマ?あまりに天才的な実装、文章から構造を整理できる気がしない。 試合テーブルの各行について試合の順番が前後してはいけない。そういうわけで、各試合に名前と矢印を付けるとグ…

GigaCode 2019 E - 車の乗り継ぎ

https://atcoder.jp/contests/gigacode-2019/submissions/13239335 これでdif12Kなのか。天才しかいない。 初期値は all(dp)=ldbl_max, dp[0]=0 繰り返しは rep(i, 1, N+2) rep(j, 0, i) 更新は dp[i] = min(dp[i], dp[j] + (ld)(car[i].x - car[j].x) / (ld…

GigaCode 2019 D - 家の建設

https://atcoder.jp/contests/gigacode-2019/submissions/13237369 長方形の全組み合わせは 長方形の全ての組み合わせについてT=土地の値段合計+面積×Kを計算し、Tが所持金V以下になる長方形のうち最大の面積が答えになる。長方形は座標P1からP4の組み合わせ…

ABC138 E - Strings of Impurity

https://atcoder.jp/contests/abc138/submissions/13182121 index[l, r]の要素数は半開区間[l, r+1)で考えると(r+1)-lで計算できる 例えば、T[2]=rをSから検索する方法を考える。これを検索するにはT[1]=hの情報が大事になる。T[1]=S[4]=hだとすると S[4]以…

パ研合宿2019 D - パ研軍旗

https://atcoder.jp/contests/pakencamp-2019-day3/submissions/13169571 DP初期値は0 DP繰り返しはrep(i, 0, N) rep(0, j, 5) DP更新はDP[i][R] = min(DP[i-1][B], DP[i-1][W]) + count[i][R]など DP出力はmin({DP[N-1][R], DP[N-1][B], DP[N-1][W]}) 入力…

ABC137 E - Coins Respawn

https://atcoder.jp/contests/abc137/submissions/11045565 最小値でなく最大値を求める場合、辺コストの符号を逆にしてグラフアルゴリズムに投げる 上記に加え、探索して得られた出力(最小値)の符号を逆にして答えとする 最大値は「符号の反転を2回する」…

EDPC R - Walk

https://atcoder.jp/contests/dp/submissions/13115881 行列の掛け算は計算量 繰り返し二乗法を使うと行列累乗(K乗)がになる 隣接行列のK乗⇔有向グラフ距離Kの経路組み合わせ数と暗記する 以上、解説終わり(ぇ 正直、行列累乗を理解したとしても凡人に応用…

ABC132 E - Hopscotch Addict

https://atcoder.jp/contests/abc132/submissions/11351529 modグラフとでも暗記すると良いかもしれない。 グラフの頂点数を3倍に増やす⇔結果を格納する配列の次元を増やすことで実現 上記に合わせてqueueもpair<ll, ll>にすると実装が楽 結果を格納する配列の初期値</ll,>…

ABC131 E - Friendships

https://atcoder.jp/contests/abc131/submissions/10950261 グラフアルゴリズムを使うわけではないので無勉でもワンチャン実装できる。 ウニグラフは距離2の頂点がn-1個できる (組み合わせは個) まず、距離2の組み合わせは真ん中の緑を除く頂点すべてを使っ…

EDPC Q - Flowers

https://atcoder.jp/contests/dp/submissions/12909348 in-place DPというやつらしい。 メイン条件 + index条件 → セグメントツリーにバラバラに入れる + RMQ (Range Max Query) 逆の逆の操作は同値「背が高い∧indexが減少」を抜く⇔「背が低い∧indexが増加」…

ABC128 E - Roadwork

https://atcoder.jp/contests/abc128/submissions/12875865 std::setのinsertと二分探索、removeが便利。 工事座標Xに到達するのにX秒かかることから逆算する。工事範囲[S-X, T-X)で二分探索してスタート時間Dの人が工事に引っかかる範囲を対応させる。ただ…

ABC116 D - Various Sushi

https://atcoder.jp/contests/abc116/submissions/9809190 数学的要素は多くないが、dif16Kなのでデータ構造の扱いが難しい。 選択済み、未選択を高速に判別するためbool型配列とprioty queueに予めコンテナを分割するテクニック 美味しさが単調減少するため…

ABC166に参加した感想

A1分、B6分、C10分、D50分、の4完だった。 1日の勉強量が少なすぎるのかもしれない…精進計画を見直すべきと考えている…。 A - A?C https://atcoder.jp/contests/abc166/submissions/12721410 テストケースが7個もあるのが不思議。 B - Trick or Treat https:…

ABC165に参加した感想

A3分、B15分、の2完でした。 プログラミング歴3日の人と同じパフォーマンスです。自殺しようと思います。 A - We Love Golf https://atcoder.jp/contests/abc165/submissions/12657284 dif1000くらいだと思います。AとBの範囲がK以上あれば必ずKの倍数になる…

ABC126 E - 1 or 2

https://atcoder.jp/contests/abc126/submissions/12464663 集合の個数はunion-findとset.insert(uf.find(Ai))で実現できる。 計算量は カードの数字が偶数と奇数に分かれるので、全部で4パターン列挙してみる。すると、Ax+Ay+ZのZが偶数でも奇数でも片方の…