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

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

各桁ごとに見る

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 ARC 103 D - Robot Arms (600 点)

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

AtCoder ARC 092 D - Two Sequences (500 点)

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

AtCoder ABC 098 D - Xor Sum 2 (500 点)

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

CS Academy 081 DIV2 C - All Numbers

解けたけどもっとちゃんと整理しないとなん 問題へのリンク 問題概要 N 個の整数 a_1, a_2, ..., a_N が与えられる (0 <= a_i <= 9)。これを並び替えて順につないでできる整数 (leading zero は除く) として考えられるものの総和を 109 + 7 で割った余りで求…