かなり悩んだ 問題へのリンク 問題概要 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だけであることを活かす解法…

オイラーツアー第4弾！！！ でもせっかくなので色んな方法で解いてみた！！！ Euler ツアー クエリの平方分割 HL 分解 重心分解 (未、todo) 問題へのリンク 問題概要 頂点 0 を根とする頂点数 N の根付き木において以下の Q 個のクエリに答えよ。なお初期状…

さあ次はいよいよ HL分解の練習をするのん！！！！！ 問題へのリンク 問題概要 N 頂点のツリーが与えられて以下の Q 個の操作を行う。初期状態では全頂点の値は 0 である。また最終的に出力する値 res の初期値も 0 とする 2 頂点 u, v 間のパス上に含まれる…

ツリー上のクエリの練習 問題へのリンク 問題概要 (意訳) N 頂点のツリーが与えられて以下の Q 個の操作を行う。初期状態では全頂点の値は 0 である。 2 頂点 u, v 間のパス上に含まれる頂点すべて (u, v も含む) の値を +1 する。 Q 回の操作後の各頂点の値…

AGC 023 A - Zero-Sum Ranges とほぼ同じ問題になってる。ただし、バケットを愚直に確保すると 109 サイズになってしまうので map とか連想配列が必要になる。 問題へのリンク 問題概要 個の整数 の連続する部分区間のうち、その総和が の倍数となっているも…

なるほど... 問題へのリンク 問題概要 整数 が与えられる。 を "-2 進法" 展開せよ。すなわち が成り立つような整数 と 0-1 整数 を求めよ。 制約 考えたこと 2 進法展開や 10 進法展開なら ここ に書いた通りなん。-2 進法になってもそう大差ないん。 基本…

LIS and LDS のバリエーション。 問題へのリンク 問題概要 1〜N の各順列について LIS (最長増加部分列) の長さが A LDS (最長減少部分列) の長さが B とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。 制約 1 <= N <= 105 …

これ、問題文を一目見て簡単な問題だと気づけるようになるには、それ自体のトレーニングが必要そうなん 問題へのリンク 問題概要 文字列 S, T が与えられる。 S のうち偶数番目だけを抜き出してできる文字列を S1 S のうち奇数番目だけを抜き出してできる文…

コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だった...... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか？ (998244…

もこもこさんが Twitter で挙げてた問題に色んな解法を寄せられていて面白かったのでメモします。 問題 を満たす整数 をすべて求めよ 解法 1: 判別式が平方数 (Pulmn さんの解法) 恐らく受験数学的には最もメジャーな解法です。 を二次方程式として見たとき…

オイラーツアー第三弾！ RUPC 2018 で見たばかりの問題でもある。 問題へのリンク 問題概要 頂点 1 を根とする頂点数 N の根付き木が与えられる。初期状態で各頂点に G または W の属性が割り振られている。以下の Q 個のクエリに答えよ: v: 頂点 v を根とす…

オイラーツアー練習第二弾。 そして、これにて一応、ツリーの辺に重みがある場合にも対応できることとなった。 問題へのリンク 問題概要 頂点 1 を根とした頂点数 N の根付き木が与えられる。初期状態では各頂点に 0 か 1 の値が割り当てられている。以下の …

オイラーツアーの練習に解いたけど、発想も面白いん！！！ 問題へのリンク 問題概要 頂点 1 を根とする、頂点数 N の根付き木がある。以下の Q 個のクエリに答えよ: M 個の頂点 v1, v2, ..., vM に実をつける。「その頂点を根とする部分木に含まれる実の個数…

これ好き！！！ 問題へのリンク 問題概要 "BCABBACCBCCACA" のような A, B, C のみからなる文字列 S の「ABC 数」とは、 S[i] = 'A' S[j] = 'B' S[k] = 'C' i < j < k を満たすような (I, j, k) の組の個数のことである。今、 ????C?????B??????A??????? の…

すごく教育的な「bit 全探索 + Greedy」！！！ 問題へのリンク 問題概要 100 点問題, 200 点問題, 300 点問題, ..., 100× 点問題がそれぞれ 問ずつある。 今、精進して合計で 点以上獲得したい。ただし、100× 点問題を 問すべて解いた場合にはボーナスとして…

人工的過ぎる設定であまり自然じゃない問題だけど、整数の整除についての注意点を学べる教育的良問ですね。 問題へのリンク 問題概要 整数 が与えられる。 を 回二乗した数より大きい最小の素数を とする。 を で割ったあまりを求めよ。 制約 < 1000 考えた…

好き系。本番解きに行ったけど、もっとサクッと通せればよかった。 問題へのリンク 問題概要 頂点の無向グラフ (頂点の番号は 1 〜 ) であって、以下の条件をすべて満たすものの個数を 1000000007 で割ったあまりを求めよ。 頂点 1 と 2 との間の最短距離が …

本番では回避したん。こういうのをサッサササッとバババババーンと解けるようになりたい。 問題へのリンク 問題概要 個の数列 が与えられる。以下の操作を好きな回数だけ行って得られる数列の総和を最大化せよ。 連続する 個の区間の数列を一斉に 0 にする …

区間の重なりを求める処理、結構久しぶりなん。 問題へのリンク 問題概要 2 で何回か割ると 140 以上 170 未満になる正の整数を「よい数」と呼ぶ。 C 以上 D 未満の整数のうち「よい数」は何個あるか求めよ。 制約 < 考えたこと まともにカウントすると間に…

星 1 個ついてるし、面白かった。「予想」を正しく立てられるかどうかがポイント。最初はカッコ列系の考察するのかと思って迷走した。 問題へのリンク 問題概要 >><><<< みたいな文字列が与えられる。最初にどこを踏んでも良い。踏んだパネルは消えて、その…

蟻さんぐるぐるなのん 問題へのリンク 問題概要 (AGC 013 C) 長さ の円周上を 匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。 匹の蟻は最初 の地点にいた。どの蟻が最初に…

高速ゼータ変換の練習第二弾！ 問題へのリンク 問題概要 長さ の整数列 があります。 を満たすすべての整数 について、以下の問題を解け: を < , を満たす整数とするとき、 の最大値を求めよ。 制約 考えたこと 個の要素を一斉に変換する何かをさせている感…

本番中なんとか解けたけど、すごくグチャグチャしたん。 問題へのリンク 問題概要 すぬけ君は、 日間にわたって、毎日次のようなパズルを解こうとしている。 すぬけ君の持っている端末に、縦 行、横 列からなる格子状の盤面が毎日配信されてくる。それぞれの…

RUPC 2018 の思い出。桁 DP。 問題へのリンク 問題概要 ごちうさ数とは、10 進法表記において「5?13」を含む正の整数のことである。? は 0〜9 のいずれでもよい。 以下の正の整数のうち、ごちうさ数が何個あるかを求めよ。 制約 解法 桁 DP。 一目、51?3 の…

なにこの 575 検出器！！！解法自体は Greedy にやるだけ 問題へのリンク 問題概要 57577 を検出せよ。 複数あるときは一番先頭を検出せよ。 do the best and enjoy today at acm icpc の場合は先頭から dothe bestand enjoy todayat acmicpc で 57577 なの…

構文解析練習第三弾。AOJ-ICPC 350 点。 問題へのリンク 問題概要 (5-3*4)*(0-2+1) のような以下の BNF で定義される計算式が与えられる: <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | * ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優</op></expr></op></expr></number></expr></expr>…

せっかく構文解析の練習を少ししたので 問題へのリンク 問題概要 -(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b)) のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうか…

構文解析、超絶苦手系だけど苦手とばかり言っていられない。 問題へのリンク 問題概要 (a)*a+((a+(a*(a))-(a)*a+a*a))*a のような文字列 が与えられる。各 a に入るデフォルトの数値 が与えられている。今 個のクエリが来て、各クエリは ： 個目の a を で置…

「前処理」を学べる問題ですね。 問題へのリンク 問題概要 色が全部で 色ある。 × の盤面がそれぞれ 色のいずれかに塗られている。今この盤面の色を塗り替えて マス () について % 3 の値によって色を類別された状態 (その値が同じマスは同じ色に、違うマス…

問題へのリンク 実は、こないだの RUPC 2018 で出てた (最後の部分のみほぼ同じ) AOJ 2873 - 検閲により置換 見た目は区間スケジューリング問題とは違うけど、実は区間スケジューリング問題 (こういうの双対問題と言ったりする)。双対性の知識がまったくなく…