お題箱より。 Problem - B - Codeforces 問題概要 英小文字からなる長さ の文字列 が与えられる。また文字列 があり、これらは最初は空である。 以下のクエリが合計で 個与えられる。 1 i c 文字列 の末尾に文字 を足す。 2 i 文字列 の末尾の文字を取り去る…

F - Absolute Minima 解法 最適な の条件 定数項 については単に答えに足すだけなので、 についてだけ考えます。 更新クエリをいくつか処理した後の式 を最小にするような の値は、 の中央値になります。これは以前の記事に説明を書いているのでそちらも参考…

E - Cell Distance 解法 この問題は結構考察ステップが多いです。順番に考えていきましょう。 数え上げの順番を変える まず考えることは「数え上げの順番を変える」ことです。抽象的な書き方ですが、これが具体的にどういうことか説明します。 問題文では以…

お題箱より。 Problem - F - Codeforces 問題概要 頂点 辺の無向グラフがあり、各辺は 色のうちどれかの色で塗られている。 以下のクエリを 個処理せよ。 + x y z 頂点 間に色 の辺を追加する。 ? x y 頂点 から頂点 までの、以下の条件を満たすパスが存在す…

お題箱より。 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip 解法 グラフの最短路問題として解けそうではありますが、異なる運営会社間での乗り換えを考慮する必要があります。つまり「どの駅にいるか」だけでなく、「その駅でどの会社の路線に乗っている…

お題箱より。 H - 根室の巫女 解法 Morris-Pratt法について まず、公式解説（？）にも書いてあるMorris-Pratt法（MP）について触れておきます。私も実戦で使ったことはないのですが…ある長さ の文字列 があったときに、全ての に対して以下の値を求めた数列 …

解説記事リクエストの募集は終了させていただきました。これまでのリクエストありがとうございました。

F - XOR Matching 解法 結論を書いてしまうと、以下のような数列がもし作れれば答えになります。 アイデアとしては、まず を挟んで 以外の数字を鏡写しに並べます。こうすることで 以外のどの数字を選んでも、2つの位置の間（両端を含む）にあるものは「 1個…

Problem - D - Codeforces 問題概要 以下の問題を 個解け。 正整数 が与えられる。以下の条件を満たす整数列 を1つ構成するか、そのような数列が存在しないことを判定せよ。 初項が で末項が である。 項数を として、全ての について とすると が成立する。…

Problem - E - Codeforces 問題概要 長さ の数列 と整数 が与えられ、 である。 以下の条件を満たす整数の組 の個数を求めよ。 である。 数列 から を満たす要素をすべて取り除くと、残った数列は広義単調増加になる。（空数列でも可） 制約 解説 削除する値…

Problem - F2 - Codeforces 問題概要 ※microtransactionは、オンラインゲームなどでのアイテム課金を指す言葉だそうです。文中では「アイテム」と訳します。 イヴァンはゲームのアイテムを買おうとしている。アイテムは 種類あり、種類 のアイテムは 個必要…

B - LRUD Game 解法 まず気付くべき点は、縦と横は独立に考えられることです。これは今回のゲームのルールが 盤外に落ちる条件が「縦座標が の範囲から外れること」または「横座標が の範囲から外れること」であること 縦座標と横座標が互いに影響し合わない…

D - DivRem Number 解法 この問題は「割り算して切り捨て」と「余り」の関連性に気付くととても考えやすくなります。実際、割り算して切り捨てたときに捨てられる部分は割った余りそのものです。 具体的に数式で表すと、 を で割った余りを とすると が成立…

ゴールデンウィークの有志コンテストなどで多く出題され、話題になったので記事を書こうと思います。 対象レートはだいたい緑～水色（最後のほうは青くらいまで）です。実際のAtCoderの問題を使って説明していくので、ネタバレになる点はご了承ください。 「…

5月4日のAGCで、ついに橙になることができました！！！ 初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。 ということで記事を書き…