競技プログラミング
問題はこちら 問題概要 解説 形式的冪級数 提出プログラム 感想 問題概要全てのの組を以下のルールでソートしたときの番目の値を求めよ.上の方が優先度が高い. の昇順. の昇順. の昇順. 解説さすがに全部列挙するのは無理.の昇順に並んでいるので,全…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要爆弾が個あり,番目の爆弾は座標にあってのときオフ,のときオンになっている.本のコードがあり,番目のコードを切ると,座標が以上以下のすべての爆弾の電源のオン・オフが切り替わる.切るコード…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要人にのつの能力値がある.この中から3人選んだときのの最大値を求めよ.解説最初に思いつくのは人の選び方の全探索.これはなので間に合わない.人決めたときにもう人を高速に決められたら解けそう…
別解です.ほぼ一緒なので丁寧には書きません.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要を並び替えてできる数列で,以下の条件を満たすものの数を求めよ. を満たす全ての数列について,の中に以下の数は個以下しか存在しない. 解説公式解…
問題はこちら 問題概要 問題概要2 解説 別解 提出プログラム 感想 問題概要頂点辺の単純無向グラフの各頂点を赤,緑,青で塗り分ける方法で隣接する頂点が異なる色で塗られているようなものは何通りあるか.問題概要2グラフ理論っぽく書かれていますが,同じ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要 を満たす整数の組全てについて の総和を求めよ.解説 形式的冪級数で解きます.とすると よってとしてが答え.を偶奇で分けると したがってBostan–Moriのアルゴリズムを用いたり,線形漸化式に直し…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要マスのマス目がある.以下の操作のうちつを選び,マスからマスまで移動するときの操作回数の最小値を求めよ. 操作:マスにいるときマスに移動する. 操作:ワープマスにいるときランダムにワープマ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要素数が書かれたカードが複数ある.そのカードをのカードに書かれた数の総和とのカードに書かれた数の総積が等しくなるように2つのグループに分けたとき,の総和(の総積)として考えられる最大の値を…
そもそも回転の列挙が難しい.以下,厳密性を欠くので注意.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要正六面体のつの面に正整数を書き込んだとき,正整数の和がとなるような物の数を求めよ.ただし,正六面体を回転して一致する書き込み方は…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要歩でちょうど距離歩けるとき,原点からまで最短何歩で行けるか.解説 とします.歩歩くとするとなら到達できないことがわかりますが,なら到達できるでしょうか?到達できそうですがのときには注意…
Mo's algorithmを用いた方法を説明します.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要英小文字からなら長さの文字列について「文字目から文字目までからなる部分文字列を任意に並べ替えたものの中で辞書順最小である文字列の文字目を出力せよ…
Mo's algorithmを用いた方法を説明します.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に関して「番目から番目までに含まれる数の種類を求めよ」という個のクエリに答えよ.解説 Range Set Queryという名前とか数列の区間に対するク…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の連結無向グラフの各辺に英小文字がつ書かれている.頂点から頂点までのウォークのうち,通った辺に書かれた文字を順に並べると回文となるようなものの回文の長さの最小値を求めよ.解説 回…
解法,解法,?解法について解説します.問題はこちら 問題概要 解説 O(√N)解法 O(logN)解法 O(1)?解法 提出プログラム 感想 問題概要以上以下の整数のうち,先頭に余分な0をつけない十進表記で偶数桁であり,前半と後半が文字列として一致するようなものは…
問題はこちら 問題概要 解説 に整数を追加する場合 から整数を削除する場合 のmexを求める ほかにも 提出プログラム 感想 問題概要長さの整数列が与えられる.の連続する長さの区間すべてについてのmexのうち最小値を求めよ.解説 最初の区間についてmexを求…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のマス目が白か黒に塗られており,塗られていないマスもある.塗られていないマスを白か黒で塗るとき,隣り合ったマスが異なる色で塗られているようなマスの組の数の最大値を求めよ.解説 隣り合っ…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要整数に対し,正の約数の個数をとする.を求めよ.思考の流れ 正の約数の個数は,素因数分解や約数を列挙することによってで求まる.からに対してこれを行うとかかる. 実際に約数の分布をみて…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点の重み無し有向グラフの隣接行列が与えられる.任意の頂点から任意の頂点までちょうど本の辺を辿って行くことのができるか判定せよ.思考の流れ yukicoder No.1340 おーじ君をさがせとほ…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要ラベル付き頂点のパスグラフから頂点を削除していく. 頂点をつ削除するたび連結成分の個数の点数を得る. 通りの削除の仕方すべての点数の総和を求めよ.思考の流れ 連結成分の数というのは数え…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点辺の有向グラフの頂点からちょうど本の辺を辿って行くことのできる頂点の個数を求めよ.思考の流れ yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を乗した行列の成分は「頂点…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの整数列が与えられる. の部分列におけるスコアをと定義する. としてあり得るすべての数列のスコアの総和を求めよ.思考の流れ を全て列挙するのは無理なのでの寄与分を考えると, からまで…
最終状態としてあり得るものの数え上げを行う問題をまとめる. 解法とかはあとでやる.目次 ARC108 D - AB ABC171 F - Strivore ABC156 E - Roaming ABC158 F - Removing Robots ARC110 E - Shorten ABC ARC107 C - Shuffle Permutation ARC108 D - AB ABC171 …
競プロ使うPythonのモジュールの使い方をメモしていきます. Counter(頻度分布) permutations(順列列挙) combinations(組合せ列挙) deque defaultdict(デフォルト辞書) Counter(頻度分布)リストや文字列を与えると要素ごとの出現頻度がわかる(辞書型みたいな…
競プロでのPythonはたとえ高速な(C++は通るような)アルゴリズムでも実装の仕方によってはTLEする(他の高速な言語に比べてしやすい). Pythonの高速化の方法について気づいたことをまとめていく. 関数化 リストの内包表記 MOD計算 deque タプル 参考 関数化な…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点の有向グラフが与えられる. グラフが空になるまで以下の操作を繰り返す. 残っている頂点のうちランダムに一つを選び, その頂点およびその頂点から辺をたどって到達できる頂点を削除する. …
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要かつはの約数でも倍数でもなく, はの約数であるような相異なる3数は何通りあるか.解説 求めるものは「かつかつかつは相異なる」ようなものの数. これを言い換えて次のものを求める「は相異なるとし…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のマスのうちいくつかを選ぶ. 行列のマスを選ぶと, 円失う. また, 行目のすべてのマスを選ぶと円得ることができ, 列目のすべてのマスを選ぶと円得ることができる. このとき最大何円得ることがで…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの数列の最長増加部分列は何通りあるか求めよ.思考の流れ すぐ思いつくのが最後にをとったときの番目まででのLISの取り出し方の総数, としたDPサンプル1(1 4 2 5 3)だとみたいになる.この…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要数直線上のの位置にあるゴミを2つ以下の座標に集める. 1回の操作につき, 座標にあるゴミをまとめてかに移動させることができる. 最小の操作回数を求めよ. また, ある座標へのゴミの追加や削除…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要座標平面上のの4点を頂点とする正方形がある. この平面上に描かれる, 座標軸に平行な線が本与えられる(軸に平行な線が本, 軸に平行な線が本). すべての線は正方形の少なくとも一辺と交差して…