結果 C - Snuke the Wizard D - Modulo Operations 結果 6 問中 2 問正解 (300 / 3300 点, 1:48)，3164 位中 547 位，パフォーマンス 1724，新レート 1520 (+25)．A, B 問題を早解き出来たので一応レートは上げることが出来たが，長い時間かけた D 問題を通…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 今黒板に書かれている数が i で，j 個 S から取り出したとき，これからの操作で考えうる最後に書かれる数の和 と DP をたてる．また，ある数字 x よりも大きい数字 y で mod をとっても x は変わらないので…

問題 解法 解答 問題 atcoder.jp 解法 答えとして知りたいのは，各ゴーレムがどこのマスにいるかではなく，マスから落ちるかどうか．また，各ゴーレムが最初の位置関係から逆転することはない（一緒の位置になることはある）．これを踏まえると，左のマスか…

問題 解法 解答 問題 atcoder.jp 解法 (a_i, b_i) というカードに対して a_i, b_i を頂点として間に辺を張ることを考える．そうすると，いくつかの輪の関係になる．ここでそれぞれの輪は共通の頂点を持ったりしない． それぞれの輪ごとに数字の種類を決めた…

問題 解法 解答 問題 atcoder.jp 解法 最大の長さの回文１つとあまりの文字で長さ 1 の回文をたくさん作るのが最適．O(|S|)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 左から i 個のブロックまでの全てを爆破済みで，区間の右端が j になるような区間で爆破するときの通り数 と DP を立てる．j <= K のとき，爆破する区間を取ることが出来ないので dp(i, j) = dp(i, j + 1) …

問題 解法 解答 問題 atcoder.jp 解法 竹を切るとき，最後に切った時刻が分かれば得点が分かる．なので，竹 L_i から竹 R_i の最後に切った時刻の総和を求められれば，各イベントの得点がわかる．最後に切った時刻は区間 [L_i, R_i] ごとに更新されるので，…

問題 解法 解答 問題 atcoder.jp 解法 各駒の縦方向・横方向の移動は独立に考えられる． ある x 座標への全ての駒の縦方向の移動量の総和を求めることを考える．ここで，決めた x 座標より小さい座標にある駒の数 cnt_up と座標の値の総和 cost_up を知れれ…

問題 解法 解答 問題 atcoder.jp 解法 dpR1(i) := 座標 i にいて，これから右に行き座標 i に戻ってこないとき，i 番目の耳以降操作しなければいけない回数の最小値 dpR2(i) := 座標 i にいて，これから右に行き座標 i に戻ってくるとき，i 番目の耳以降操作…

問題 解法 解答 問題 atcoder.jp 解法 まず，A 枚のクッキーを B 枚のクッキーにするとき，2 枚以上増えなければ得をしない．なぜならば，2 回かかる操作をただクッキーを 1 枚あたらしく得ることに費やした方がよいから．そうでないとき，まずクッキーを A …

問題 解法 解答 問題 atcoder.jp 解法 頂点をいくつかのグループに分けるとき，全てグループに含まれる頂点の数字の和が S になるように N 個の頂点をグループ分けし，それらのグループを互いに全て結べば答えが求められる．N が偶数の時，(1, N), (2, N - 1…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k, l) := 今 i - 1 文字目まで考えて，i - 3 文字目が j，i - 2 文字目が k, i - 1 文字目が l のときの，i 文字目から先の通り数 と DP を定義する．次の１文字（すなわち i 文字目）を決めるとき 'A', 'T', …

問題 解法 解答 問題 atcoder.jp 解法 N, Q <= 10^5 より，各クエリごとに文字列を走査していては間に合わない．そこで，各クエリに O(1) で答えられるようにする． imos_i := i 文字目までに登場する "AC" の数 とおくと，各クエリで求める値は imos_r - im…

問題 解法 解答 問題 atcoder.jp 解法 前から操作を見るのは実は困難なので，後ろから見ていく．このとき，問題は「場所 i で数字 i を消すことができる．この消し方とは？」と言い換えられる．また，消す場所は消せる場所の中で一番右がよい．なぜならば，…

（個人用のメモにつき解読不能です） <Minerals>・小課題１C(2N, 2) 個のペアについて全部試すO(N^2) 回装置を使う ・小課題２O(NlogN)ぐらいなら通るか分割統治で再帰てきに解く半分に分けたものを全て機械に入れるもう片方から１つ持ってきて種類数が増えるか増えな</minerals>…

（個人用のメモにつき解読不能です） 機械学習ゲーム以外にも様々な応用強化学習のプログラムは特にゲーム AI で多く登場する他にも自動運転やロボット操作などにも応用される ベンチマークOpenAI Gym という制御問題，物理シミュレーション，Atari ゲームな…

問題 解法 解答 問題 yukicoder.me 解法 ツーリストチケットはツアーの中で１回しか使えないので，行きか帰りかのどちらかで使うことになる．なので，頂点 1 から各頂点へツーリストチケットを使って行くときの最小コストと，使わないで行くときの最小コスト…

問題 解法 解答 問題 yukicoder.me 解法 まず，各頂点の次数を求める．これは，A, B に対して map を使ってもいいし，ただの配列でいい．これで求まった次数のうち，3 以上のものに関して操作をしたい．3 以上のものに関しては 2 まで次数を減らさなくてはい…

＜Lamps＞・小課題１全状態を探索する0, 1 の状態は 2^N 通り，各状態からの遷移は O(N^2) 通りBFS で O(2^N * N^2) 時間で分かる ・小課題３初期状態が全部 0連続する 1 の区間の個数回の操作でできる（各区間で ON か TOGGLE をする）それ未満ではできない…

（個人用のメモにつき，解読不能です） 充足可能性問題 (SAT)論理変数 True か False論理式 論理変数と NOT, AND, OR で出来た式与えられた論理式 f(x, y, … , z) が True となるような x, y, … , z の割り当ては存在するか？存在するとき：SAT（その割り当…

（個人用のメモにつき解読不能です） ＜Two Transportations＞・小課題１A = 0Azer の辺が無い全ての辺が Baijan にある→ Baiijan は都市 0 からの距離が分かるBaijan が距離を求める距離を Azer に送る N <= 2000Dijkstra法 O( (N + B) logB)N < 2^11，（重…

（個人用のメモにつき解読不能です） 機械学習の基本 たくさんのデータが与えられ，データから規則を見つけ，その規則を使って新しいデータについて予想する ２番目を自動的に行うのが機械学習 分類問題の例：迷惑メール分類 迷惑メールとそうでないメールの…

（個人用のメモです） 大規模グラフとは プログラミングコンテストでも頻出 世の中もグラフだらけ ソーシャルネットワーク（Twitter, Facebook など） 人が頂点，友達関係が辺 道路網 交差点同士を結ぶ道路 Web リンク Web ページを頂点，リンクを辺とみれる…

（個人用のメモです，間違いがある可能性があります） Examination 小課題１ 小課題２ 小課題３ 小課題４ 別解１：二次元セグ木 別解２：定数倍高速化 得点分布 Naan 小課題１ 小課題２ 満点 得点分布 Meetings 小課題１ 小課題２ 小課題３ 別解 得点分布 Ex…

（個人用のメモです．「この文章は解読不能です」） 数列 A_1, A_2, ... , A_N に対する以下のクエリに答えよ． ・A_l ~ A_r それぞれを X と AND をとる ・A_l ~ A_r それぞれを X と OR をとる ・A_l ~ A_r の min 取得 ただし，X は 64 bit 非負整数．set…

問題 解法 解答 問題 codeforces.com 解法 b_i を「頂点 i を根とする全て部分木に含まれる s の最小値」とおく．このとき，b_i < s_i であるような頂点が存在したらその木は構成不可能なので -1 を出力すればよい． 木が構成出来る場合，木全体を根から（す…

問題 解法 解答 問題 codeforces.com 解法 縦長のタイルは 4x4 のマスの上半分，横長のタイルは下半分にひたすら敷き詰めていけば永遠に敷き詰められる．なぜなら，上半分に関しては 4 つ設置すると上から 1, 2 行目が消えて，下半分に関しては 2 つ横に並べ…

問題 解法 解答 問題 yukicoder.me 解法 ２つ目の条件式の左辺に x, y, z の 3 文字，右辺に w の 1 文字となっていて全探索するには O(N^3) かかってしまい間に合わない．そこで，この式を変形して，x^2 + y^2 = -z^2 + w^2 + D とすることで左辺・右辺の取…

問題 解法 解答 問題 atcoder.jp 解法 １回の操作でどこか１つの bit を反転させるので，A と B の立っている bit 数の偶奇は必ず違う．なので，偶奇が同じ場合は必ず操作を構成できないので NO．逆に偶奇が異なる場合は必ず構成できる． 再帰的に構成を求め…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := i 個目の石までの塗り方の数 とする．このとき，i 個目の石と同じ色の石が j (j < i) 個目にあるとき，[j, i] の区間を i 個目の石の色で塗ることが可能．塗るときの塗り方の数は考えられる j について dp(j -…