けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ

AOJ 3369 Namori Counting (OUPC 2023 day2-D)

北大セットの D 問題。人生で初めて行列木定理を使った! 問題へのリンク editorials 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。 今、このグラフにおいて連結性を保ったまま 本の辺を削除する。そしてこのとき閉路が 1 個残るので、閉路…

AOJ 4003 演算装置の接続 (PCK 2022 本選 4)

次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…

AOJ Course GRL_6_B 最小費用流

最小費用流アルゴリズムを実装したときの verify に 問題へのリンク 問題概要 頂点数 、辺数 のフローコストネットワークが与えられる。 番目の辺は頂点 から頂点 へ張られていて、容量は 、単位流量あたりのコストは である。 頂点 を始点、頂点 を終点とし…

AOJ Course GRL_6_A 最大流

最大流アルゴリズムを実装したときの verify に 問題へのリンク 問題概要 頂点数 、辺数 のフローネットワークが与えられる。 番目の辺は頂点 から頂点 へ張られていて、容量は である。 頂点 を始点、頂点 を終点とした最大流値を求めよ。 制約 考えたこと …

AOJ 1282 Bug Hunt (ICPC アジア 2007 H) (450 点)

アドホックに構文解析した。カッコ列の問題とみなして、stack で処理した。 問題へのリンク 問題概要 次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。 a[2147483647] a[0]=1 B[2] B[a[0]]=2 a[B[a[0]]]=3 a[2147…

AOJ 0109 スマート計算機 (PCK)

至ってシンプルな構文解析問題。ただちょっと仕様が不明瞭なところがある気もする。 問題へのリンク 問題概要 次のように、何個かの計算式を表す文字列 が与えられるので計算結果を出力せよ。 2 4-2*3= 4*(8+4+3)= 式は数値、演算記号、かっこからなり、= で…

AOJ 1346 Miscalculation (ICPC アジア 2014 B) (200 点)

アドホックにも実装できそうだけど、構文解析ライブラリで殴った! 問題へのリンク 問題概要 0 以上 9 以下の整数値に対して「+」「×」で連結して得られる長さ の文字列 が与えられる。たとえば以下のような文字列が与えられる。 1+2*3+4 また、Bob がこの式…

AOJ 2426 Treasure Hunt

BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…

AOJ 1549 Hard Beans (ACPC 2014 day2-I)

Wavelet Matrix の prev_value や next_value が使える問題! 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 が与えられるので、数列の区間 の値のうち、 との差の最小値を答えよ。 制約 考えたこと Wavelet Matrix の関…

AOJ Course RSQ and RUQ (遅延評価セグメント木の練習問題 4)

「区間値更新」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x): を に変更する クエリタイプ (1 s t): の総和…

AOJ Course RSQ and RAQ (遅延評価セグメント木の練習問題 3)

「区間加算」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x): に を加算する クエリタイプ (1 s t): の総和を…

AOJ Course RMQ and RUQ (遅延評価セグメント木の練習問題 2)

Starry Sky Tree は「区間 加算」「区間最小値取得」を処理する遅延セグ木だった。 今回は「区間 更新」「区間最小値取得」を処理する遅延セグ木を実装する。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は…

AOJ Course RMQ and RAQ (遅延評価セグメント木の練習問題 1)

この問題は、人生で最初に挑む遅延セグ木の問題としてオススメ!Starry Sky Tree と呼ばれるものでもある。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s…

JOIG 2023 C - 鐘 (AOJ 0759, 難易度 4)

直線がいくつかの区間に分かれているとき、点がどの区間に属するかを求めたいとなったら、lower_bound()!!! 問題へのリンク 問題概要 数直線上に 個の鐘がある。 番目の鐘は座標 の地点に配置されている。 地点 の人の聞く鐘の音の強さは、各鐘 に対する …

JOIG 2023 B - 絶対階差数列 (AOJ 0758, 難易度 2)

いわゆる「愚直シミュレーション」と呼ばれる分野の問題ですね。問題文で指示されたことを、とにかく愚直に忠実に実装できるかが問われています。地味な印象を受けるかもですが、大切なスキルです! 問題へのリンク 問題概要 黒板に、はじめ 個の整数値 が書…

JOIG 2023 A - 末尾の文字 (AOJ 0757, 難易度 1)

文字列の練習! 問題へのリンク 問題概要 英大文字のみからなる、長さ の文字列 が与えられる。 の末尾の文字が 'G' 以外のとき: の末尾に文字 'G' を挿入して得られる文字列を の末尾の文字が 'G' であるとき: の末尾の文字 'G' を削除して得られる文字列…

JOI 予選 2007 F - 通学経路 (AOJ 0515, 難易度 4)

DP の典型問題だけど、最初は難しく感じるかもしれない。あと、縦横が微妙に混乱するね。 問題へのリンク editorial 問題概要 (今風に表現改) のグリッドが与えられる。このグリッドで上から 番目、左から 番目のマスを と書くことにする。最初、マス に駒が…

JOI 予選 2007 E - 品質検査 (AOJ 0514, 難易度 5)

この辺りから難しくなって来てる。「 で合格・不合格」という条件をどのように適切に言い換えるかが問われている。 問題へのリンク 問題概要 電源が 個、モーターが 個、ケーブルが 個ある。電源は と番号づけられていて、モーターは と番号づけられていて、…

JOI 予選 2007 D - カードの並び替え (AOJ 0513, 難易度 3)

難しくはないけど、やることが複雑だし、問題文を読み解くのがハードな問題! この手の問題は、解けないと思ったら、実際のコードを見てしまう方が早いと思う。 問題へのリンク editorial 問題概要 正の整数 が与えられる。 1 から までの数値が書かれたカー…

JOI 予選 2007 C - シーザー暗号 (AOJ 0512, 難易度 2)

アルファベットを戻す処理を書くのが最初は難しいかもしれない 問題へのリンク editorial 問題概要 シーザー暗号とは、文字列に対して、各文字を 3 つずつ進めたものに変換するものである。ただし、X, Y, Z はそれぞれ A, B, C となる。具体的には、次のよう…

JOI 予選 2007 B - 未提出者は誰だ (AOJ 0511, 難易度 2)

for 文を二重にしたり、フラグを管理したりする練習! 問題へのリンク editorial 問題概要 個の整数値が与えられる。これらの整数値は 以上 以下の整数から 2 個を除外したものとなっている。 その除外された 2 個の整数値を小さい順に答えよ。 考えたこと …

AOJ 2369 CatChecker (JAG 冬合宿 2010 day3-A) (300 点)

カッコ列の整合性判定問題の亜種と言える。 問題へのリンク 問題概要 文字列 が cat 文字列であるとは、次の条件を満たすことをいう。 は空文字列である ある cat 文字列 が存在して、 と表せる 与えられた文字列 が cat 文字列であるかどうかを判定せよ。 …

AOJ 2373 HullMarathon (JAG 冬合宿 2010 day3-E) (700 点)

面白い最適化問題! 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…

AOJ 0461 奇数の精と偶数の精 (PCK 2021 予選 問題 9)

少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね! 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…

AOJ 3333 Range Xor Query (HUPC 2023 day1-J)

Binary Trie + 平方分割 問題へのリンク editorials 問題概要 数列 に対して、以下の 個のクエリを処理せよ。 クエリタイプ 1 (k x): を xor に置き換える クエリタイプ 2 (l r x): xor の値を出力する 制約 考えたこと これは TL で解法を見た上で解いた…

AOJ 2567 SIRO Challenge (JAG 模擬地区 2013 C) (400 点)

「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題! 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは …

AOJ 2828 マトリョーシカ (JAG 模擬国内 2017 F) (550 点)

DAG の最小パス被覆、忘れた頃に出て来るイメージ! 問題へのリンク editorials 問題概要 個の直方体があり、 番目の直方体の大きさは である。 今、ある直方体の中に他のある直方体を入れたりすることで、外部から見えている直方体の体積を小さくしたい。た…

AOJ 2293 Dangerous Tower (JAG 夏合宿 2011 day2-D) (600 点)

めっちゃ面白い問題! 問題へのリンク editorials 問題概要 個の直方体がある。 番目の直方体は の形をしている。 今、これらの直方体からいくつかを選んで積み木を作る。このとき、奥行き方法は必ず長さが になるようにする。 縦または横方向については、 …

AOJ 1088 School Excursion

最小費用の最大流を流すネットワークフロー問題! 問題へのリンク editorial 問題概要 個の駅があり、 と番号づけられている。 駅 と駅 の間には 種類の電車が走っていて、 番目の電車は 駅 を時刻 に出発して、 駅 に時刻 に到着し、 料金は である。 今、 …

JOI 二次予選 2023 A - 年齢の差 (AOJ 0747, 難易度 3)

シンプルながらも、学べるポイントがたくさんある問題ですね 問題へのリンク 公式解説へのリンク 問題概要 JOI 市には から までの番号が付けられた 人の住民がいて、住民 () の年齢は 歳です。 JOI 市の住民の年齢 ​ が与えられます。 に対して、住民 と他…