競技プログラミングで使用する ビットごとの排他的論理和 の性質の雑多なメモ

問題. New Elements: Part 1 2種類の原子からなる 個の分子が与えられる． 番目の分子を1種類目と2種類目の原子の個数の対 で表す．このとき，分子量が狭義単調増加するような 個の分子の並べ方が何通りあるか求めよ．ただし，分子量とは分子に含まれる原子…

問題. 高橋君と禁断の書 2辺の長さが の矩形 が与えられる．次の 個の質問に答えよ． 質問：2辺の長さが の矩形 が与えられたときに， が を含むか判定せよ制約： ，

問題. The minimal unique substring 文字列の部分文字列に対して，その部分文字列の出現回数がちょうど1回のときユニークな部分文字列と呼ぶ．正整数 が与えられる．ただし， とする．0 と 1 からなる長さ の文字列で，ユニークな部分文字列の長さの最小値が…

問題. XOR Partitioning 数列 が与えられる． の空でない連続部分列への分割で，その連続部分列のビットごとの排他的論理和がすべて等しくなるようなものが何通りあるかを求めよ．制約： ，

問題. 同一円周上 平面上に 個の格子点がある．マンハッタン距離でこれらの格子点からの距離が等しくなる格子点を求めよ．制約： ，

問題. Bacterial Tactics 縦 行，横 列の長方形のマス目が与えられる．各マスは空白か危険な物質が置かれている．2人のプレイヤーが交互に空白のマスを選び V型かH型のバクテリアを置くことを繰り返す．V型バクテリアは置かれたマスの隣接する上下方向の空白…

問題. Power Arrangers ABCDE の5文字からなる順列は 通りある．その中から1つの順列を取り除いた119個の順列を適当な順番に並べた列 がある（ は未公開）．「 の 番目の文字が何か」というクエリを高々 回行い取り除かれた順列を求めよ．制約：

問題. Removing Coins 頂点の木が与えられる．初めにすべての頂点に1つのコインが置いてある．2人のプレイヤーが交互に次の操作を行う．操作の行えないプレイヤーを負けとする． コインが置いてある頂点 を1つ選び， にあるコインを取り除く．そして 以外の…

問題. LRUD Game 縦 行，横 列の長方形上のマス目の に駒が置かれている．高橋君と青木くんはそれぞれ長さ の文字列 を持っている．高橋君から交互に駒を動かさないか，または，文字列にしたがって動かすかを決める．高橋君が ターン目に動かすことのできる…

問題. Fair Fight 非負整数 と2つの非負整数列 が与えられる．組 で を満たすものがいくつあるかを求めよ．制約： ，

問題. Draupnir -day ring と呼ばれる指輪がある．1つの -day ring は出現した日から 日ごとに -dary ring を1つ複製するということを永遠に続ける．0 日目に各 -day ring が 個出現する（ は未公開）． 「 日目にある指輪の総数の による剰余はいくつか」と…

問題. Manhattan Crepe Cart の格子上に 人がいる． 番目の人は にいて東西南北のいずれか （順番に 'E', 'W', 'S', 'N'）を向いている．すべての人はクレープ屋に最小の移動距離で移動しようとしている．ただし，距離はマンハッタン距離である．多くの人が…

問題. 花束 個の赤い花と 個の青い花がある． 個の赤い花と1個の青い花からなる花束と，1個の赤い花と 個の青い花からなる花束の2種類の作り方がある．作ることのできる花束の個数の最大値を答えよ．制約： ，

三分探索 (Ternary search) は 単峰関数の大域最適解 連続関数の極小値 を求める反復解法である．次の問題を三分探索で解く．＊ 「連続関数の極小値」ではなく「単峰（たんほう）関数の大域最適解」と修正しました．詳細は一番下に書きました．（2020年11月2…

問題. Golf Gophers 18ホールあるゴルフ場の各ホールにちょうど1つの風車がある．毎晩， 番ホール（）にある風車のブレード数を任意に に決めて， 0 番目のブレードが真下にあるように設定する．ただし，ブレードは時計回りに と番号付けされている． 各風車…

問題. Polynomial Divisors 次の整数係数多項式 が与えられる．任意の整数 に対して が の倍数となるような素数 をすべて求めよ．制約： ， ，

問題. Three Colors 個の整数 が与えられる．与えられたすべての整数を赤，緑，青の3色のいずれかで塗るとき，次の条件を満たすような塗り方が何通りあるかを答えよ． 赤，緑，青で塗られた整数の和をそれぞれ R, G, B としたとき，3辺の長さを R, G, B とし…

問題. Alien Rhyme 英大文字からなる 個の単語が与えれる．各単語に任意に1つアクセントを付ける．アクセントから末尾までの部分文字列をその単語のアクセント接尾辞と呼ぶことにする．2つの異なる単語が同じアクセント接尾辞を持つとき，それらの単語は韻を…

問題. Handstand 長さ の 0 と 1 からなる文字列 と非負整数 が与えられる． の連続する区間を任意に選び，その区間に含まれる 0 と 1 を反転するという操作を高々 回行う．そのとき，連続する1 からなる区間の長さの最大値を答えよ．制約：

問題. Dat Bae 台のマシンがあり， から までの番号付がなされている．それらのマシンの内 台が壊れている．次で定義するマスタとの間のインタラクティブな通信を高々 回行いどのマシンが壊れているかを特定せよ． インタラクティブな通信とは，長さ の 0 と…

問題. ABC013 D：阿弥陀 本の縦線と 本の横線からなるあみだくじが与えられる．このあみだくじを縦に 個つなげる．左から 番目の縦線を選んであみたくじを行ったときの結果が下端で左から何番目にあるのかを答えよ． 制約： ， ，

問題. Modulo Operations 個の相異なる自然数からなる集合 と自然数 が与えられる．初期値を として次の操作を 回行う． から任意に要素 を1つ選んで取り除き，現在の値 を に更新する． の任意の取り除き方によって得られる 回の操作後の値の総和を求めよ．…

問題. 正直者の高橋くん 頂点の連結無向グラフ が与えられる． から への最短経路数を答えよ．制約：

問題. Deforestation 1 から までの番号付けされた 本の竹がある．時刻 0 において全ての竹の高さは 0 で，時刻が 1 経過するごとに各竹の高さが 1 伸びる． 回のイベントがあり， 番目のイベントでは時刻 に番号が 以上 以下の竹を伐採する．このときに伐採…

問題. Erasure 左から 1 から までの番号が付いた 個のブロックが一列に並んでいる．長さ 以上の連続する区間のブロックを削除という操作をすべてのブロックが無くなるまで繰返し行う．そのような操作の集合が何通りあるのかを求めよ．制約： ，

問題. Pass 人のすぬけ君がそれぞれボールを2個ずつ持って1列に並んでいる．ボールの色はそれぞれ赤か青のどちらかである．各ステップで自分の持っているボールをどれか1つ前の人に渡すというステップを 回行う．先頭の人が選んだボールの色の列としてありう…

問題. Ears 数直線上を次を満たすように連続的に移動する． ・移動可能な場所は 0 以上 以下 ・整数座標の点からスタートして整数座標の点でゴールする ・整数座標の点でのみ方向転換可能 整数座標の点 に対して， を通過すると に1点が加算される． が与え…

問題. 掛け算の最大値 正の偶数 が与えられる． を満たす正の整数 で の最大値を求めよ．制約：

問題. 高橋君と青木君の好きな数 正の整数 が与えられる． 以上の と の公倍数で最小の数を求めよ．制約： ，