7K4B blog

猫でも分かる何か

2020-01-01から1年間の記事一覧

ABC179 に参加した感想

A2分、B3分、C7分、の3完。 11週間連続目標に届かなかった。ため息しか出ない。 明らかに頭が悪いのが原因であって努力不足ではないと思う。 https://atcoder.jp/contests/abc179/submissions/16849595 頑張ってタイピングする https://atcoder.jp/contests/…

ABC178に参加した感想

A1分、B4分、C14分、D34分、の4完 緑difを高速に解く数学力が足りないせいで一生水色になれない…自分の半分以下の精進で自分より遥かに高いパフォーマンス出してる人たちが散見され悲しくなる A - Not https://atcoder.jp/contests/abc178/submissions/16681…

ABC177 に参加した感想

A1分、B7分、C9分、D8分、E56分、11WAの5完だった。 5完しても1079しかパフォーマンスが出ない。精進不足なんだよな。 A. Don't be late https://atcoder.jp/contests/abc177/submissions/16314199 頑張ってタイピングする。 B. Substring https://atcoder.j…

ABC133 D - Rain Flows into Dams

https://atcoder.jp/contests/abc133/submissions/15728517 と続く方程式は2変数に減らせる 「奇数個」の循環方程式(上記方程式が循環)は1変数に減らせるので答えが分かる 山iの降水量を、ダムiの水量をとする。 ... となるので、奇数番目のを加算、偶数番…

ABC134 D - Preparing Boxes

https://atcoder.jp/contests/abc134/submissions/15708918 1, 2, 3, ... の倍数毎に調べる要素数は調和級数になっている 後ろから情報を確定していく i+1以降の箱のうち倍数iの箱だけ考える。(i+1以降の)倍数iの箱に入っているボールの合計をsとしたとき…

ABC174 に参加した感想

A1分、B2分、D50分、1WAの3完 勝率0%のパチンコ?糞では? A - Air Conditioner https://atcoder.jp/contests/abc174/submissions/15597894 頑張ってタイピングする B - Distance https://atcoder.jp/contests/abc174/submissions/15595040 std::hypotって知…

第9回日本情報オリンピック 本選 A - 旅人

https://atcoder.jp/contests/joi2010ho/submissions/15527888 半開区間にすれば、そのまま宿の距離になる 制約から移動距離をO(1)で求めたいので累積和にする。移動開始をs、移動終了をt、としたとき移動がマイナスだと区間が[t, s)となってしまうが、[min(…

全国統一プログラミング王決定戦本戦 A - Abundant Resources

https://atcoder.jp/contests/nikkei2019-final/submissions/15652985 累積和にすることで区間和をO(1)で処理できる 半開区間で処理することで[l, l+range)の累積和が答えになる 制約から各kの答えをで処理しなければならない。例えばk=500のとき[0, 500)か…

square869120Contest 1 E - 散歩

https://atcoder.jp/contests/s8pc-1/submissions/15582396 半開区間はデータの境界を表す 制約から1個のクエリを未満で処理する必要がある。街Aから街Bへ移動するとき移動距離は半開区間[A, B)で表される。したがって、半開区間そのまま累積和で加算処理し…

AOJ NTL_1_B Power

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4728976 繰り返し二乗法を使うと累乗は mのn乗をするのにn回だけ掛け算するのは制約からTLEする。 二乗した値を二乗することで木構造と同じ理由でで計算できるようになる。

ABC006 D - トランプ挿入ソート

https://atcoder.jp/contests/abc006/submissions/15555175 ソートするためには最低でも最長増加部分列(LIS)以外は移動する必要がある マージソートなどは木構造を使って1枚あたりの計算量をに減らすが、これは計算量を求める問題ではない。どんなソートを…

AOJ DPL_1_D Longest Increasing Subsequence

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4726957 最長増加部分列の計算量は 小さい数字に貪欲に更新することで部分列の長さが増加する可能性を増やす。二分探索したときendであれば、その数字を追加することで長さが1増える。更新するべきか…

ABC135 D - Digits Parade

https://atcoder.jp/contests/abc135/submissions/15552119 桁DPで処理する 初期値は dp[0][0] = 1 繰り返しは rep(i, 1, Size(S)) 更新は if (S[i] == '?') rep(j, 0, 13) rep(k, 0, 10) dp[i][(j * 10 + k) % 13] += dp[i - 1][j] など 出力は dp.back()[5…

ABC137 D - Summer Vacation

https://atcoder.jp/contests/abc137/submissions/15521766 x日後を前から見るのでなく、後ろから見たほうが条件が狭くなる (後ろから)x日以内に報酬を貰えるバイトのうち最大を貪欲に選べばok x日後を前から考えるより後ろから考えたほうが条件が狭くなる…

ABC138 D - Ki

https://atcoder.jp/contests/abc138/submissions/15508780 根の値 < 部分木の値に必ずなる⇒累積和 制約から各クエリを以下で処理しなければならない。根の値が伝搬されて必ず「根の値 < 部分木の値」になることから累積和になっていることが分かる。DS_Nyaa…

ABC140 D - Face Produces Unhappiness

https://atcoder.jp/contests/abc140/submissions/15507196 https://atcoder.jp/contests/abc140/submissions/9416948 任意区間に対して人の位置を反転させた上で向きも反転させる 反転したとき「連続文字列をグループ化した個数」と「幸福度」の増減に着目…

CPSCO2019 Session1 D - Dessert Planning

https://atcoder.jp/contests/cpsco2019-s1/submissions/15476330 DPでシミュレーションして数列の一般項を求める 初期値は dp[0][0] = dp[0][1] = 1 繰り返しは rep(i, 1, 3 * N) 更新は dp[i][0] += (dp[i - 1][1] + dp[i - 1][2]); など 出力は Sum(all(d…

CPSCO2019 Session1 C - Coins

https://atcoder.jp/contests/cpsco2019-s1/submissions/15470682 Kが小さいのでK種類の商品を全探索する 大きい硬貨から貪欲に支払いを構成する Nが32なので全探索はできないが、Kが最大6なので個の全探索は出来そうという気持ちになる。小さい硬貨で支払う…

ABC084 D - 2017-like Number

https://atcoder.jp/contests/abc084/submissions/15381403 素数テーブルと2017に似た数字の前処理をしておくことで各クエリをにする 制約から各クエリを以下で処理する必要がある。範囲クエリをで処理する方法として累積和を使いたくなる。素数テーブルを用…

AOJ NTL_1_A Prime Factorize

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4693828 素因数分解の計算量は Nを2から順番に割っていって因数を求める。このとき割る数はまでで良い。もし、以上の数字aで割れるとすると商bは以下になる。もし、aとbが両方以上だとN < abとなるた…

2010年 日本情報オリンピック春合宿 - Finals

https://atcoder.jp/contests/joisc2010/submissions/15253528 最小全域木のうち最長の辺をK-1個だけ取り除いてK個のグラフに分ける K個の開催都市を何処にするかは無関係(一度に複数人通行させれば料金一律なので) 辺をK-1個だけ取り除くことでグラフをK…

AOJ GRL_2_A Minimum Spanning Tree

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4213849 クラスカル法による最小全域木の計算量は 最小全域木は全ての頂点を通るグラフの最短距離となる。最小全域木のアルゴリズムにはプリム法とクラスカル法がある。実装方法は蟻本p100に載ってい…

ABC141 D - Powerful Discount Tickets

https://atcoder.jp/contests/abc141/submissions/15353189 priority_queueのtop、pop、pushを多用しリアルタイムに最大値を取得、更新する この類の問題は買う値段などを決め打ちして二分探索するような定跡もあるが、今回はokとなる値が不明となるため二分…

ABC142 D - Disjoint Set of Common Divisors

https://atcoder.jp/contests/abc142/submissions/15352890 https://atcoder.jp/contests/abc142/submissions/15351653 因数分解した因数の組み合わせが約数になる 素因数分解した因数の個数 ⇔ 約数のうち素数の個数 「互いに素でなければならない」という条…

ABC145 D - Knight

https://atcoder.jp/contests/abc145/submissions/15338725 ベクトルの個数が分かれば格子状の最短経路問題と同じ (i+1, j+2)と(i+2, j+1)のベクトルs,tの個数が分かっていれば、格子状の最短経路問題と同じ。ベクトルの個数は連立方程式で求まる。連立方程…

ABC 152 E - Sum of gcd of Tuples (Hard)

https://atcoder.jp/contests/abc162/submissions/14903598 gcd=t の決め打ち 緩和した条件なら簡単に計算できる 降順に答えを求めるとメモ化が役に立つ 上記結果とメモ化した答えを足したり引いたりすることで設問の答えを得る ではTLEするので、gcd=tとな…

ABC147 D - Xor Sum 4

https://atcoder.jp/contests/abc147/submissions/13626753 https://atcoder.jp/contests/abc147/submissions/15303781 「集合nと集合mの片道は全部でn×m個」=「完全二部グラフ」=「辺の数はn×m個」 制約からが許されないので、ビット桁ごとに処理して計算…

ABC151 D - Maze Master

https://atcoder.jp/contests/abc151/submissions/13015367 https://atcoder.jp/contests/abc151/submissions/15292083 スタート地点が#の時どこにも移動できないので何もせず結果を返すことに注意 制約が縦横20しかないことからやが許される。つまり、スタ…

ABC152 D - Handstand 2

https://atcoder.jp/contests/abc152/submissions/15125443 条件X∧Yを満たす値の個数を二次元配列[X][Y]で管理する 先頭X末尾Yとなる値の個数をbcount[X][Y]とする。1からNまで線形処理すればbcount[1][1]からbcount[9][9]までの個数は得られる。あとは先頭S…

ABC012 D - バスと避けられない運命

https://atcoder.jp/contests/abc012/submissions/10345521 max(始点v[i]から目的地v[j]への最短経路)がminになるバス停v[i]を見つける つまり全点対間最短経路を求めればok 最大値の最小値が答え。つまりバス停について、に引っ越した時の最大値、に引っ越…