2019-03-01から1ヶ月間の記事一覧
問題 解法 解答 問題 atcoder.jp 解法 各ブロックについてそのブロックの重さが答えに加算される回数を求めたい．ブロック i の重さが加算される回数を求める．ブロック i とブロック j が連結である場合の数を P(i, j) とおく．P(i, j) (1 <= j <= N) の和…
問題 解法 解答 問題 yukicoder.me 解法 全ての商品をお金を出して買うとすると，答えは (A_1 + A_2 + ... + A_N) + (B_1 * 0 + B_2 * 1 + B_3 * 2 + ... + B_N * (N - 1)) となる．この式から，B が小さい順に早く購入した方がよいことが分かる．なので，B …
問題 解法 解答 問題 https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 解法 k 日目までに感染の広がる様子をシミュレーションする．流行している都市から感染が拡大する範囲が d <= 25 と狭いので，現在流行している都市それぞれを…
問題 解法 解答 問題 www.ioi-jp.org 解法 カードの枚数に対してシャッフルの回数がとても少ないので，ほとんどバラバラにならない．なので，連続する数字が書かれるカードを１つの区間としてもっておき，その区間をシャッフルによって切ったり，並び替えた…
問題 解法 解答 問題 https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf 解法 ある横の辺を消すということは，その辺を通る２つのパスの中のその辺の高さ以降のパスが逆になることを意味する．ゆえに，任意の横の辺を消したとき，ある２つ…
問題 解法 解答 問題 https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf 解法 1 ~ (N - 1) 回目にたどり着いた場所を知る必要はない．また，詳しいルートを１回ずつ区別して計算する必要はない．なぜならば，N 回目のルートやたどり着く場…
問題 解法 解答 問題 https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf 解法 各事務所についてどれぐらいの数の部屋をどれぐらいの認証レベルで入ることが出来るのかが知りたい．ここで，各事務所のマス上で BFS をする．具体的には，(今…
問題 解法 解答 問題 https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf 解法 数列 A を書き出して実験してみると，1 ~ (m * 2^m) 項目の偶奇が周期的に繰り返していることが分かる．１つの周期の中にいくつ奇数の項があるかを数え，(…
問題 解法 解答 問題 atcoder.jp 解法 グラフから辺を取り除いていくのではなく，辺を追加していくと考える．辺を後ろから追加していった時の「不便さ」を逆にしたものが求める答えになる． 辺を１つ追加したときに改善される「不便さ」は辺の両端の頂点それ…
問題 解法 解答 問題 atcoder.jp 解法 各クエリごとに x_i より左にある最寄りの神社・寺，x_i より右にある最寄りの神社・寺の場所を計算する．これは std::lower_bound() や std::upper_bound() を用いて O(logA), O(logB) で計算できる．あとは，神社と寺…
結果 C - Energy Drink Collector D - XOR World 結果 ４問中４問正解（1000 / 1000 点, 27:05），3152 位中 163 位．C 問題で実装ミスをしてしまい 1 WA してしまったのが痛い... C - Energy Drink Collector babcs2035.hateblo.jp D - XOR World babcs2035…
問題 解法 解答 問題 atcoder.jp 解法 A, B >= 10^12 と大きいので愚直な計算では TLE となってしまう． ここで，答えとなる数の k bit 目を明らかにすることを考える．0 から順番に数を 2 進数表記で書いて眺めてみると，1 bit 目は 0, 1, 0, 1, ... と 0, …
問題 解法 解答 問題 atcoder.jp 解法 どの店も１本ごとに値段が決まっているので，１本ごとの値段が安い店から順番に出来るだけ買うのが最適．M 本買えるまで安い順に店を当たっていく．ソートがボトルネックとなり O(NlogN)． 解答 atcoder.jp くだらない…
