Codechef Cook 101 で自分が解いた部分までの解説です (Div2 の4問目、Div1の3問目まで)。 各問題にはテストケース数 の制約があるけど省略しています。 Camp Or Not 概要 競プロキャンプに向けて問題を解く。 問題を解くスケジュールは 日決まっていて、 日…
CodeChef Cook100で解いた問題の解説です(div2の4問目、div1の3問目まで)。 Truth and Dare Contest Page | CodeChef 概要 集合が与えられる。 かつ のとき "yes"と、そうでないとき"no"と答えよ。 解法 set<int> で集合を管理して愚直に部分集合になっているか調</int>…
この前AtCoderで非公式コンテストがあったけれども、メールはないし公式のカレンダーにも載ってなかったので 危うく出損ねるという事案があった。 非公式だししょうがないかなぁというのもあるけどやっぱりカレンダーは欲しいので自前で作った。 GitHub - ok…
問題 D: LCM Rush - AtCoder Beginner Contest 020 | AtCoder が与えられるので を計算せよ。 解法 となるので後はの約数 ごとにとして が計算できればいい。 式変形が何をしているかと最後の総和の計算は解説 Editorial - AtCoder Beginner Contest 020 | A…
この記事は 解説 Advent Calendar 2017の24日目の記事です。 adventar.org 以下のコンテストの解説です。 www.hackerrank.com はじめに 競プロ!!Advent Calendarのこの記事 (競プロにおけるNim、Grundy数とNimK - かっさのなにか)に 触発されて書きました(と…
最近Ruby on Rails チュートリアル:実例を使って Rails を学ぼうを終えてRubyの練習がてら競プロの問題をいくつか解いてみたので、 入出力の方法とかのメモ。 他に関連しそうな記事: Rubyで競技プログラミング - yhara.jp Rubyの入出力 - ヘクトのメモ 入出…
概要 問題文 頂点数の単純無向グラフが与えられる。 また各頂点には値が割り当てられている。 このとき、頂点を含む独立集合のうち値の総和の最大値を求めよ。 制約: 解法 半分全列挙+高速ゼータ変換 (想定解法ではないらしい)。 頂点を半分に分けて、を含む…
概要 問題文 電車で目的地まで行くための最短経路を求めるというよくある感じの問題。 本の路線がありそれぞれの路線は個の駅からなる。 一つの路線について駅とそれらの間の所要時間が与えられる。 電車は両方向にあるのでどちら向きに移動しても良い。 ま…
概要 問題文 自然数列 に対して以下の操作を 回行ったときの先頭の数字を答えよ。 先頭から 番目の数字を削除する。 制約: 解法 下のように、ある数字が削除される前は先頭から何番目だったか逆から構成していくと分かりやすい。 削除前 012…k-1kk+1k+2… 削…