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

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

辞書順

AtCoder AGC 048 A - atcoder < S (緑色, 300 点)

単純な探索でも解けるし、考察で計算量を減らすこともできそう。 問題へのリンク 問題概要 文字列 が与えられる。文字列 に以下の操作を最小回数行うことで、辞書順で > "atcoder" となるようにせよ。 中の連続する 2 文字を swap する (このテストケースが …

AtCoder AGC 022 A - Diverse Word (茶色, 300 点)

ある程度探索でゴリ押した。 問題へのリンク 問題概要 英小文字のみからなり、どの 2 文字も互いに相異なる文字列を「多彩」であると呼ぶこととする。多彩な文字列 が与えられる。以下の条件を満たす文字列の中で最も辞書順が小さいものを求めよ。 よりも辞…

AOJ 2584 壊れた暗号生成器 (ICPC 模擬国内 2014 C) (400 点)

BNF が書かれているので、LL(1)文法を再帰降下とかするのが標準みたいだけど、ad-hoc にスタックでなんとかしてしまった 問題へのリンク 問題概要 以下の BNF によって定義された文字列が与えられる。 <Cipher> ::= <String> | <Cipher><String> <String> ::= <Letter> | '['<Cipher>']' <Letter> ::= '+'<Letter> | '-'<Letter> | 'A' | 'B' |</letter></letter></letter></cipher></letter></string></string></cipher></string></cipher>…

AOJ 2295 Power of Power (JAG 夏合宿 2011 day2-F) (550 点)

コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…

AOJ 2679 Decoding Ancient Messages (JAG 春コン 2014 C) (700 点)

多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…

AtCoder AGC 043 C - Giant Graph (赤色, 900 点)

これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…

Educational Codeforces Round 83 G. Autocompletion

頑張って DFS だけで通した!!! 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…

Codeforces Round #618 (Div. 1) C. Water Balance (R2100)

これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…

第5回 ドワンゴからの挑戦状 本選 2019 B - XOR Spread (800 点)

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …

AOJ 2630 Dictionary (JAG 夏合宿 2014 day2-B) (550 点)

最初は「え!? i 行目の文字列情報がないと i+1 行目以降のことを考えられなくない?」となってしまって、途方に暮れてしまった 問題へのリンク 問題概要 個の文字列 があって、それぞれいくつかの文字は '?' で隠されている (したのは の例) '?' 全体をア…

CODE FESTIVAL 2016 qual A C - 次のアルファベット / Next Letter (緑色, 400 点)

辞書順最小の教育的例題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に以下の操作をちょうど 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。 の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる 制約…

AOJ 2423 コードアートオンライン / Code Art Online

最小包含円と、マッチングの二部構成問題 問題へのリンク 問題概要 個の円 ( と番号付けされている) と、 個の多角形 ( と番号付けされている) とが与えられる。 各円は、中心の座標と半径 各多角形は、各頂点の座標 が与えられる。すべての多角形が、いずれ…

Codeforces #613 (Div. 2) D. Dr. Evil Underscores (R1800)

こういう貪欲に突き進む処理を書くの、実はかなり苦手かもしれない 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。上手に正の整数 を選ぶことで、 XOR XOR ... XOR の値の最大値の最小値を求めよ。 制約 考えたこと 最小値を求めたいということ…

AtCoder ABC 150 C - Count Order (茶色, 300 点)

next_permutation の練習になりそう。DFS でも。 問題へのリンク 問題概要 の順列 が与えられます。 が の順列のうち辞書順で何番目か が の順列のうち辞書順で何番目か を求め、それらの差を答えよ。 制約 考えたこと 制約が小さいので、 通りの順列をすべ…

第6回 ドワンゴからの挑戦状 予選 D - Arrangement (橙色, 800 点)

今回は惨敗したけど次回また頑張りたい!!! 問題へのリンク 問題概要 の順列であって、以下の条件を満たすもののうち、辞書順最小のものを求めよ。存在しない場合は -1 を出力せよ。 の右隣の値は ではない 制約 考えたこと 色々手を動かしてみると、条件…

第5回 ドワンゴからの挑戦状 予選 2018 B - Sum AND Subarrays (水色, 400 点)

最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…

Codeforces Round #584 - Dasha Code Championship F. Koala and Notebook (R2600)

勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…

AtCoder ABC 141 F - Xor Sum 3 (黄色, 600 点)

Xor Sum シリーズしゃん。典型てんこ盛り!!! XOR は各桁ごとに独立に考えるとよい XOR に関する問題は mod. 2 での方程式みたいになることも多い であることから上位の桁から辞書順的に優先で考えるような貪欲が決まる などなど。 問題へのリンク 問題概…

AtCoder AGC 001 F - Wide Swap (2000 点)

これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…

AOJ 1392 Shortest Common Non-Subsequence (ICPC アジア 2018 D) (500 点)

ARC 081 E - Don't Be a Subsequence の文字列が 2 個になったバージョン! 問題へのリンク 問題概要 2 つの '0' と '1' で構成された文字列 S, T が与えられる。 S の部分文字列でも T の部分文字列でもないような文字列のうち長さが最小のものを求めよ。複…

AOJ 1399 Sixth Sense (ICPC アジア 2018 K) (500 点)

「辞書順最大」という条件さえなければ典型的な Greedy マッチングではあるね。「辞書順最大」になっても頑張れば基本に忠実にできる。ややこしいけど頑張ればできる感じかな。。。 問題へのリンク 問題概要 人対 人の対戦割当を決めたい。敵が 1 回戦、2 回…

AtCoder AGC 029 C - Lexicographic constraints (黄色, 700 点)

弱かった。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 文字列の列 であって の文字数が である 辞書式順序で < < < を満たすもののうち、登場文字数の最小値を求めよ。 制約 考えたこと が狭義単調増加だったら、"a" の個数だけで行けるので…

AtCoder ARC 081 E - Don't Be a Subsequence (黄色, 600 点)

部分列 DP の考え方を試せる問題 問題へのリンク 問題概要 (ARC 081 E) 文字列 A が与えられる。 A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。 複数考えられる場合にはそのうち辞書順最小のものを求めよ。 制…

AtCoder AGC 026 E - Synchronized Subsequence (赤色, 1600 点)

こういうのちゃんと解き切れるようになりたい... なんだろ、「'a' と 'b' の個数が等しくなるような区間ごとに分割する」という発想がちゃんと出て来るようにするためには、どういう流れの考察をすればよいのだろう... 問題へのリンク 問題概要 N 個の 'a' …

AtCoder ABC 097 C - K-th Substring (ARC 097 C) (緑色, 300 点)

本番出てなかったけどこれは... ARC 097 C K-th Substring 問題概要 文字列 s が与えられる。s の連続する部分文字列のうち、辞書順で K 番目の文字列を求めよ。 制約 1 <= |s| <= 5000 1 <= K <= 5 解法 K が小さいのが怪しい。 冷静に考えると、辞書順 K …

CS Academy 079 DIV2 C K - Inversions

CSA 079 DIV2 C K Inversions 問題概要 1 ~ N の順列で転倒数が K となるもののうち、辞書順最小のものを求めよ。 2 <= N <= 105 0 <= K <= NC2 やったこと 辞書順最小ということで、とにかく今見ている部分を極力小さくする Greedy を行う。 具体的には、…

CS Academy 069 DIV2 B - Reverse Subarray

B なのに難しかったのん。 CSA 069 DIV2 B Reverse Subarray N 要素からなる数列が与えられる。 ここから連続する区間を reverse することで元の数列全体が単調非減少となるようにしたい。 そのような区間の選び方は何通りあるか? またそのような区間のうち…