atcoder.jp 概要 最大10万長の文字列Sが与えられる。"yahoo"を0以上の任意の整数回繰り返した文字列とSの編集距離の最短を答えよ。

atcoder.jp 概要 最大30万枚のかーどがあたえられ、一枚のカードにはそれぞれ1~30万の数字がある。あなたはこの中からK枚のカード選び、それらを取り除く。この操作は何回できるだろうか？ただし、Kは1からNまですべて試しそれぞれ出力すること。

tdpc.contest.atcoder.jp 概要 人のレーティングはそれぞれ設定されていて、人 i が人 j に勝つ確率は。 人1, 2, 3, 4, ..., 2^Kの順に並び、それぞれ平衡二分木になるようなトーナメントを組む(詳細は問題文参照)。 人1, 2, 3, 4, ..., 2^Kの順に優勝する確…

atcoder.jpこの問題から、次のような一般化された問題を考える。 問題文 N個のものを考える。高速でそのうちの1つを抜いた時の計算結果を求める。

atcoder.jp 概要 N(N )個の町をM(M )本の道がつないでる。それぞれの道には距離D(D )が設定されてる。あなたの車は最初燃料L( L )まで積んでおり、距離1走るごとに燃料1を消費する。町で燃料の補給ができるが、道の途中で燃料を切らしてはいけない。Q( Q )個…

onlinejudge.u-aizu.ac.jp 概要 (0, 0), (W - 1, 0), (0, H - 1), (W - 1, H - 1)を頂点に持つ長方形の座標領域内に、N個の重複しない点がある。(1 あなたは最初に(0, 0)にいる。次の行動が任意回行える。 1, x座標、もしくはy座標を1増減させる。(もちろん…

atcoder.jp 概要 二回のコンテストが行われ、それぞれの参加者は∞人いた。高橋くんは一回目でa位、二回目でb位を取った。 この時、スコアをある参加者の二回のコンテストの順位の積と定義する。 高橋君よりスコアが上の参加者は最大何人いるのだろうか？ AC…

atcoder.jp 概要 長さN(N 入力されるある整数K(1 ある数Xを含む部分集合のうちのすべての「良い集合」で、X自身を除いても「良い集合」となるとき、Xは「「良い集合」を作るのに不必要」と言います。 さて、「不必要」な要素はいくつあるでしょう？ちなみに…

atcoder.jp 概要 数直線上にN個(N にあり、昇順で与えられる。 で、を満たすの組み合わせの数を求めよ。

atcoder.jp 概要 文字列S, T(長さが最大 10^5)は'A', 'B'のみで構成されてる。 あなたは、 1. A -> BB , B -> AAに置換 2. AAA ->(nothing), BBB -> (nothing) と、3つ連続の同じものを消す ことを好きな回数だけ行える。この時、Q回(1 Sの[a, b]をTの[c, d]…

atcoder.jp 問題概要 N人の人でトーナメントして、引き分けなしの勝負をした。最終的に勝ったのは人1である。人2～人N(2

atcoder.jp 概要 100文字までの文字列SをK(1

atcoder.jp 問題概要 n のk個の集合に分ける。集合に含まれる頂点は、番号がちょうど一つ前と後の集合、に含まれる点とすべて辺でつながっていないといけないし、集合から出てる辺もまたすべてと連結するのに必要十分でないといけない。このような振り分け方…

問題文atcoder.jp 問題概要 長さN、要素が最大10^18の数列がある。あなたはK回、このうちの要素のうちの1つを選んで、それを2で割って商を切り捨てる。 K回操作を終えた時、数列のバリエーションを10^9+7で割ったあまりで求めよ。操作の手順が違っても最終的…

前回の記事読了の方はお疲れ様でした。今回は高速フーリエ変換の実装とその具体例について書きます。

はじめに 学生最強コンのAが高速フーリエ変換そのものであると聞き、高速フーリエ変換を勉強しました。ネット上のフーリエ級数、変換の資料をあさりつつ、tsutajさん、Atcoder社の公式解説をいろいろ眺めて理解に努めようとしたが、頭が弱いため完全理解には…

atcoder.jp 問題概要 長さNの数列で、1 区間において、すべての要素のxorと和が等しい(l, r)の組の数を数え上げよ。N

atcoder.jp因数定理の合同による式変形を知っていれば命題の同値条件でサクサク行く問題であった。その先にも少してこずるものもあり、800点としては妥当だと思う。(水色の雑魚が言ってる)この問題、はじめにxは任意の整数という条件になってる。ここで、受…

atcoder.jp O(1)atcoder.jp O(log B)[A,B]の区間の自然数をすべてXORしたらいくつになるでしょう？XORは同じものを重ねると0になり、0はXORの単位元なのでいくらあっても演算結果に影響がないので、累積和の要領で差分みたいなのをとればいい。また、解説に…

atcoder.jp LCS(Longest Common Subsequence)をもとめよう。 典型典型と言ってるわりに以外に詰まった問題。反省しろ。 文字列の中身を1文字目, 2文字目, 3文字目...とすると dp[i][j]: 一つ目の文字列が i 文字目まで、二つ目の文字列が j 文字目まで見た時…

atcoder.jp 前回の続き。 しばらく普通のしゃくとりの例題と実装を説明するので上の問題の解説はしばらく後。 普通のしゃくとり法 普通のしゃくとり法は、条件を満たす区間の中で最善になる可能性のあるものを、区間の両端を動かすことにより求める。 たとえ…

atcoder.jp 最大20万の長さの自然数列を与えられ、そこにしきりを3ついれて、4つに分割する。4つの数列の和の最大値と最小値の差を最小化するとき、その差はいくつになるか。 例） 5 2 3 6 1 3 2 ベストな分割方法は{5}, {2, 3}, {6}, {1, 3, 2}にして和は5,…

arc073.contest.atcoder.jp ナップサック問題に制約、 Wがばかでかいので当然普通のdpではMLEする。 ここでＮが小さいときに注目、Ｎが小さいときにうまくいくのは全探索、全列挙的な手法となる。 100では全列挙は厳しいけど、ここで、重さは４通りしかない…

このブログは @Senの競技プログラミング備忘録です。コケた問題などを自戒のために載せて解説する（つもり） 間違えてるところや質問などがありましたらぜひおねがいします