裏紙

ほぼ競プロ、たまに日記

CS Academy

CS Academy #42 - Xor Submatrix

問題 CS Academy 問題概要 長さの配列と長さの配列が与えられる。これらから、の行列を作る。で行列の各項を与える。 この中で部分行列を取り出し、その部分行列の要素の全てのXORを取る時に、得られる値の最大値を求めよ。 アイデア 部分行列の左上隅のinde…

CS Academy #44 - Array Elimination

問題 CS Academy 問題概要 要素数の配列が与えられる。いま、配列のindexを1つ指しているポインタがあり(はじめは)、そのポインタに対して以下の3つの操作ができる: を1増やす を1減らす が指している位置の要素を削除し、は1つ前の要素か1つ後の要素を指す…

CS Academy #41 - Candles

問題 CS Academy 問題概要 本のろうそくがある。番目のろうそくの長さはである。一晩ろうそくを使用すると長さは1だけ減る。 これから、回の夜を過ごそうとしている。日目の夜には、本のろうそくを灯そうと考えている。最大で過ごせる夜の回数を求めよ。 ア…

CS Academy #40 - Direct the Graph

問題 CS Academy 問題概要 頂点数の完全グラフの各辺に対して向きを付ける(トーナメント)。この時、経路長が3である閉路の個数が最大になるように向きを付け、その向きの付け方と、その結果経路長が3である閉路はいくつになるか答えよ。 アイデア まず、問題…

CS Academy #38 - Tree Antichain (Hard)

問題 CS Academy 問題概要 頂点数の木が与えられる。長さの順列を考え、それを頂点に対応させる時、との間にいずれも辺がないような順列の中で辞書順最小のものを求めよ。 テストケース数 : テストケース全体でのの和はを超えない アイデア 同じラウンドに(E…

CS Academy #14 - Subarrays Xor Sum

問題 CS Academy 問題概要 長さの数列が与えられる。長さが以上以下の部分列に対して、xorを取った値の和をで割った余りを答えよ。 アイデア ビットごとに独立に考えていく。今、ビットを固定する(とする)と、もとの数列は01の数列として見なすことができる…

CS Academy #20 - Palindromic Concatenation

問題 Archive 問題概要 文字列が個与えられる。番目の文字列をと表す時、との連結(この順番に並べて結合した文字列)が回文になるような組の個数を求めよ。 は英小文字のみで構成される とは区別される アイデア が回文になる時、どのような状況になれば条件…

CS Academy #1 - Unfair Game

問題 https://csacademy.com/contest/archive/#task/unfair_game/ 問題概要 個の整数で構成される集合がある。この集合を使ってAlexとBenはゲームを行う。Alexが先手、Benが後手となって交互に自分のターンを行うが、このゲームでは先手と後手ではできる行動…