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

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

各桁ごとに見る

AtCoder ABC 326 B - 326-like Numbers (灰色, 200 点)

整数 が 326-like 数かどうかを判定する処理が書ければ、この問題は解ける。 問題へのリンク 問題概要 整数 が 326-like 数であるとは、3 桁の正の整数であって、百の位と十の位の積が一の位に等しいことをいう。 与えられた整数 以上の、最小の 326-like 数…

yukicoder No.2032 Let's Write Multiples!!

floor sum の練習! 問題へのリンク 問題概要 以上 以下の の倍数をすべて十進表記で 1 回ずつ書き出した時、数字 が書かれる回数を求めよ。 (テストケースが 個与えられる) 制約 考えたこと 各桁ごとに考える。整数 の右から 桁めが である条件は を で割っ…

AtCoder ABC 283 Ex - Popcount Sum (橙色, 600 点)

floor sum と聞いて!! 問題へのリンク 問題概要 以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。 ( ケース与えられる) 制約 考えたこと TL を見て、floor sum と知った上での考察。 「popcount の総和…

AtCoder ABC 281 F - Xor Minimization (青色, 500 点)

数列に対して、2 進法で表して、再帰的に上位桁から 0 と 1 で分類した木を作る!!! こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…

AtCoder ABC 196 C - Doubled (灰色, 300 点)

いわゆる、 まで調べれば十分というタイプの問題だね。最近そのタイプの問題が流行っている気がする! 問題へのリンク 問題概要 十進法表記で偶数桁で、かつ、その前半と後半とが文字列として等しいようなものを「良い整数」と呼ぶことにします。 以上 以下…

Codeforces Round #673 (Div. 1) C. XOR Inverse (R2000)

バチャ中に TLE が取れなかった... で実装してしまっていたけど、 にする必要があったみたい。 問題へのリンク 問題概要 長さ の 0 以上の整数からなる数列 が与えられる。 0 以上の整数 を適切に定めて XOR で定まる数列 の転倒数が最小となるようにせよ。…

JOI 春合宿 2007 day3-1 anagram (難易度 6)

桁DPとは違うけど、桁DP的な発想で解けた ジャッジページへのリンク 問題概要 長さ の文字列 が与えられる。 の各文字を並び替えてできる文字列をすべて考えたとき、 はその中で辞書順で何番目の文字列に相当するのかを求めよ。 制約 の文字はすべて英大文字…

Codeforces Round #683 (Div. 1) C. Xor Tree (R2100)

こどふぉのこの回、いい問題が多かった気がするので解き直し。最上位の桁から順に見ていって、0 と 1 とに分類していって...とするのはよく見る気がする!!! 問題へのリンク 問題概要 どの要素も互いに相異なる非負整数列 が good であるとは、以下の条件…

Codeforces Round #687 (Div. 1) B. XOR-gun (R2000)

こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。 問題へのリンク 問題概要 長さ の正の整数からなる広義単調増加な数列 が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。 数列の隣接する 2 つの要素を選んで、…

AtCoder ABC 042 C - こだわり者いろはちゃん (ARC 058 C) (緑色, 300 点)

記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題!!! 問題のリンク 問題概要 以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。 制約 考えたこと 真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいず…

CPSCO2019 Session3 E - Enumerate Xor Sum (500 点設定)

これ、てんぷら君のおかげで随分とシンプルな問題になった! 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。各 に対して、 xor xor xor としたときの xor xor xor の値を求めよ。 制約 解法 XOR に関する問題は各桁ごとに考えるのは常套手段では…

AOJ 2566 Restore Calculation (JAG 模擬地区 2013 B) (350 点)

これが生まれて初めての作問だった!!! AOJ-ICPC で ☆4 個ついてて嬉しい! 問題へのリンク editorial 問題概要 虫食算が与えられる。解の個数を 1000000007 で割ったあまりを求めたい。 より正確には長さ の 3 個の文字列 が与えられる。これらは '?' か …

AtCoder AGC 015 D - A or...or B Problem (橙色, 900 点)

最初、「これは本当に AGC か!??」となってた 問題へのリンク 問題概要 以上 以下の整数の中からいくつか選んで、OR 和をとってできる値が何通りあるか求めよ。 制約 考えたこと 一見するとこどふぉっぽい見た目の問題だけど、実はすごく AGC っぽい感じ…

AtCoder ABC 147 D - Xor Sum 4 (水色, 400 点)

考え方自体は典型的ではある 問題へのリンク 問題概要 個の整数 が与えられる。 これらから 2 個選んで XOR をとって得られる整数 ( 個ある) の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと XOR をみたら、とにかく「各桁ごとに考える」とい…

Educational Codeforces Round 84 F. AND Segments (R2500)

実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…

Codeforces Round #626 (Div. 1) B. Present (R2100)

確かに AtCoder で完全既出だった! drken1215.hatenablog.com 問題へのリンク 問題概要 要素の数列 が与えられる。これらから 2 つ選んで和をとって得られる 個の整数の XOR 和を求めよ。 制約 #include <bits/stdc++.h> using namespace std; const int INF = 1<<30; int </bits/stdc++.h>…

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

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

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

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

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

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

AtCoder ABC 129 F - Takahashi's Basics in Education and Learning (橙色, 600 点)

重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…

AtCoder ABC 129 E - Sum Equals Xor (水色, 500 点)

まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…

GCJ 2019 Qual A - Foregone Solution

面白かった 問題へのリンク 問題概要 100 桁以下の整数 が与えられる (文字列型で受け取るのがよさそう)。 も も十進法表記で '4' が登場しない を満たすような整数 の組を 1 つ求めよ。 制約 < < 考えたこと 繰り上がりを考えると面倒なので、繰り上がりが…

yukicoder No.803 Very Limited Xor Subset

F2 線形代数大好き! 問題へのリンク 問題概要 個の整数 の部分集合を選んで XOR 和を にする方法のうち、 個の区間 [ ] () について 区間の中から選ぶ個数は偶数個か奇数個かが指定される という制約を満たすものが何通りあるか求めよ。 制約 考えたこと 実…

AtCoder ABC 121 D - XOR World (緑色, 400 点)

みんな早い...!!! 問題へのリンク 問題概要 2 つの整数 () が与えられる。 以上 以下のすべての整数の XOR 和を求めよ。 制約 「A 以上 B 以下」と、「XOR の引き算」とは まず「 以上 以下の値の総和を求めよ」という問題は、「 以下の値の総和を求めよ…

桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか 〜

K 以下の整数を分類する 今日の ABC D 問題 で話題になったので書いてみます。競プロで 非負整数 が の範囲を動くときの、〜〜〜の最大値を求めよ 非負整数 が の範囲を動くときの、〜〜〜という条件を満たすものは何通りあるか という形をした問題は非常に…

AtCoder ABC 117 D - XXOR (水色, 400 点)

以下の典型思考で解けるけど、苦手意識...^^; XOR な問題は各桁ごとに見る の動ける範囲が 以下と指示されているときは、 を上位ビットから見ていったときに、それがどこまで と一致するかを考える (桁 DP でおなじみの考え方) 問題へのリンク 問題概要 個の…

Tenka1 2018 C - Align (緑色, 400 点)

今週のお題「わたしとバレンタインデー」 提出するまでが怖かった 問題へのリンク 問題概要 整数が N 個与えられます。 i 個目の整数は Ai です。 これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。 考えたこと うおっ…

AtCoder ABC 111 D - Robot Arms (ARC 103 D) (橙色, 600 点)

くやしい 問題へのリンク 問題概要 個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて (), (), (), () をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。 各 について共通の を用いなければな…

AtCoder ABC 091 D - Two Sequences (ARC 092 D) (黄色, 500 点)

桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 091 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…

AtCoder ABC 098 D - Xor Sum 2 (ARC 098 D) (水色, 500 点)

こんなしゃくとり法もあるのんな。面白いん。 ABC 098 D Xor Sum 2 問題概要 長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。 制約 数値例 1) 答え: 5 (2), (2, 5), (5),…