はまやんはまやんはまやん

hamayanhamayan's blog

Deforestation [全国統一プログラミング王決定戦本戦 D]

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d 前提知識 遅延評価セグメントツリー(区間add, 区間代入→区間sm) 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4314272この問題は区間add,区間代入,区間総和get…

Come Together [全国統一プログラミング王決定戦本戦 C]

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c 前提知識 BIT 二分探索 マンハッタン距離についての知識 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4312922まず、この問題を考える糸口だが、「マンハッタン…

Big Integers [全国統一プログラミング王決定戦本戦 B]

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_b 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4312776与えられた式はよく見てみると、K進数の数になっている。 そのため、K進数で与えられた数の大小を答えよと…

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

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_a 前提知識 累積和 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4312713累積和を知っていれば、それぞれの整数Kについて全探索できると分かる。 練習のために尺取…

Match Matching [AtCoder Beginner Contest 118 D]

https://atcoder.jp/contests/abc118/tasks/abc118_d 解説 https://atcoder.jp/contests/abc118/submissions/4287467嘘解答の可能性があります最適方針として、なるべく桁数を増やしたほうがいいことは分かる。 そのためには、一番少ない本数で作れる数をた…

Monsters Battle Royale [AtCoder Beginner Contest 118 C]

https://atcoder.jp/contests/abc118/tasks/abc118_c 前提知識 GCD、ユークリッドの互除法 解説 https://atcoder.jp/contests/abc118/submissions/4280971競技プログラミングは時にはエスパー力が求められる。 エスパーをすると、全部のgcdが答えになりそう…

Foods Loved by Everyone [AtCoder Beginner Contest 118 B]

https://atcoder.jp/contests/abc118/tasks/abc118_b 解説 https://atcoder.jp/contests/abc118/submissions/4280142データの渡し方が後から扱うのにシンプルではないので、扱いやすいように入れ替える。A[i][j] := i番目の人がj番目の食べ物が好きなら1, 無…

B +/- A [AtCoder Beginner Contest 118 A]

https://atcoder.jp/contests/abc118/tasks/abc118_a 解説 https://atcoder.jp/contests/abc118/submissions/4278906問題で要求されていることをそのまま実装する。 自分は以下のように実装した。 int A, B; //--------------------------------------------…

Arithmetic Progression [Codeforces Round #538 (Div. 2) E]

https://codeforces.com/contest/1114/problem/Eインタラクティブ問題。 初項X0, 交差D, 項数Nの数列がある。 この数列がランダムな順で入った配列Aがある。 項数Nの情報と、以下のクエリを60回以下行うことで、X0,Dを見つけよ。操作1 : 「? i」A[i]の要素を…

Please, another Queries on Array? [Codeforces Round #538 (Div. 2) F]

https://codeforces.com/contest/1114/problem/FN要素の配列Aがある。 これについて以下のクエリをQ回行う。操作1: "MULTIPLY l r x" A[l], A[l+1], ..., A[r]全てにxをかける 操作2: "TOTIENT l r" φ(A[l]*A[l+1]*..*A[r]) mod 10^9+7を答える φ(x)はトー…

Flood Fill [Codeforces Round #538 (Div. 2) D]

https://codeforces.com/contest/1114/problem/DN要素の色の配列Cがある。 ある要素を指定する。 指定の要素から以下の操作を何回か行って全ての色を同じにせよ。 操作「指定の要素と連結している(同じ色でつながっている)領域をある色に変える」1≦N, C[i]…

Trailing Loves (or L'oeufs?) [Codeforces Round #538 (Div. 2) C]

https://codeforces.com/contest/1114/problem/CN!をB進数で表記したときに、末尾に0が何個続くか。 1≦N≦10^18 2≦B≦10^12 解説 https://codeforces.com/contest/1114/submission/49705240Bを素因数分解したときに、p1^e1*p2^e2*...となったとする。 この時、…

Yet Another Array Partitioning Task [Codeforces Round #538 (Div. 2) B]

https://codeforces.com/contest/1114/problem/BN要素の配列Aがある。 この配列を「連続していてM要素以上の列」にK個に分ける。 分割後の各列について、大きい方からM個取ってくる。 取ったMK個の総和の最大値を求めて、分割地点を答えよ。2≦N≦2*10^5 1≦M 2…

Odd Subrectangles [「みんなのプロコン 2019」 E]

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_e 前提知識 mod2上でのガウスの消去法(掃き出し法) 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4221314本当にちゃんと解きたい場合は線形代数…

Ears [「みんなのプロコン 2019」 D]

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d 前提知識 連結DP 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4212545今回の問題は一筆書きをしたときに通る回数と要求される回数との差を最小…

When I hit my pocket... [ 「みんなのプロコン 2019」 C]

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_c 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4207345交換操作をするためにはA枚にはする必要があるので、A枚までは叩いて増やそう。 この過程で…

Path [「みんなのプロコン 2019」 B]

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_b 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4206062通るパターンを全探索しよう。 4つの街で訪れる可能性のあるパターンは4!通りなので、これ…

Anti-Adjacency [「みんなのプロコン 2019」 A]

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_a 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/42037511~Nで差が1にならないように選ぶには飛び飛びで選んでいくのがいい。 つまり、N/2の切り上…

範囲の合計 [yukicoder No.789]

https://yukicoder.me/problems/no/789 前提知識 動的構築セグメントツリー 解説 https://yukicoder.me/submissions/315636このクエリは動的構築セグメントツリーで解決できるので持ってる人は貼るのが最速。 持っていない場合は、今回はクエリ先読みできる…

トラックの移動 [yukicoder No.788]

https://yukicoder.me/problems/no/788 前提知識 ダイクストラ 考察過程 1. かなり難しい問題に見えるので、小さいことから紐解いていく 2. M≦2000が気になる(普通なら10^6くらいじゃない?) 3. この制約なら、全ての頂点間の距離を求められる 4. とりあえ…

Mice and Traitors(ネズミ達と裏切り者) [yukicoder No.787]

https://yukicoder.me/problems/no/787 解説 https://yukicoder.me/submissions/315634条件付き確率で解く。 P,Qは÷100して確率にしておく。 答えはP(裏切り|裏切りっぽい)となるので、 P(裏切り|裏切りっぽい) = P(裏切り∩裏切りっぽい) / P(裏切りっぽい) …

京都大学の過去問 [yukicoder No.786]

https://yukicoder.me/problems/no/786 前提知識 動的計画法(組み合わせ系) 解説 https://yukicoder.me/submissions/315631dpで解く。 dp[i] := i段目に到達するまでの登り方の組み合わせ数 すると、遷移は dp[i + 1] += dp[i] // 1歩で1段 dp[i + 2] += d…

色食い虫 [yukicoder No.785]

https://yukicoder.me/problems/no/785 解説 https://yukicoder.me/submissions/315630ある色について、使えない文字がn種類あった場合は、使える文字は16-n種類となる。 ある色は2桁で表現されるので、この場合は(16-n)^2通りの表現ができることになる。 答…

「,(カンマ)」 [yukicoder No.784]

https://yukicoder.me/problems/no/784 解説 https://yukicoder.me/submissions/315624数字を文字列として見ると、後ろから3つ毎にカンマを入れる処理となる。 これを実装しよう。 実装を簡単にするために、「与えられる数は文字列として考えて処理」 「反転…

XXOR [AtCoder Beginner Contest 117 D]

https://atcoder.jp/contests/abc117/tasks/abc117_d 前提知識 桁DP 解説 https://atcoder.jp/contests/abc117/submissions/4166833桁DPをする。 2進数で60桁を想定して解く(10^12なので、もうちょっと小さいが、横着した)。 dp[dgt][isless] := 上位dgtビ…

Streamline [AtCoder Beginner Contest 117 C]

https://atcoder.jp/contests/abc117/tasks/abc117_c 解説 https://atcoder.jp/contests/abc117/submissions/4162169隣接する点に移動するというのと、ソートできるときは大体したほうがいいので、Xをソートする。 まずは最適行動について考えてみよう。 す…

Polygon [AtCoder Beginner Contest 117 B]

https://atcoder.jp/contests/abc117/tasks/abc117_b 解説 https://atcoder.jp/contests/abc117/submissions/4160902便利な定理が提示されているので、それをそのまま実装しよう。 Lをソートして、一番長い辺以外の総和と一番長い辺を比べて答えを出そう。 i…

Entrance Examination [AtCoder Beginner Contest 117 A]

https://atcoder.jp/contests/abc117/tasks/abc117_a 解説 https://atcoder.jp/contests/abc117/submissions/4160726世界A→世界Bで×Xなので、 逆なら/Xとなる。 つまり答えはT/X。 小数なのでdouble型とかで計算しよう。 色々注意点はあるが、 T,Xは小数型に…

FightMonsterDiv1 [SRM749 Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=15296体力HPの敵がいる。 自分の初期攻撃力がattackで、攻撃するたびに(初期attack)*level/100だけ増える。 (つまり、増える量は常に固定) 1度だけスペル詠唱が可能で、スペル詠唱後はduratio…

Restore the Tree [全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 D]

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d 前提知識 トポロジカルソート 解説 https://atcoder.jp/contests/nikkei2019-qual/submissions/4101570まず、N頂点の木があり、ある頂点uからその子孫vに辺がはられている。 これは全…