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

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

TopCoder

TopCoder SRM 604 D1E PowerOfThree

平衡三進法!!! 問題へのリンク 問題概要 二次元座標平面上で、(0, 0) から出発して へと移動したい。何ステップかの移動を行うことができる。 ステップ目の移動では、上下左右のいずれかの方向を一つ選んで、 だけ移動することができる (いずれかの方向に…

TopCoder SRM 400 D1E StrongPrimePower

詰めるの大変だった。こういうの 240pt で通せる人ってどうなってるの!? 問題へのリンク 問題概要 2 以上の整数 が与えられる。 が狭義の素数べき (素数 と 2 以上の整数 を用いて と書ける数) であるかどうかを判定し、素数べきの場合には の値を求めよ。…

TCO 2013 Round 2A Med TheMagicMatrix

mod. p での連立一次方程式の練習などに!!! 問題へのリンク 問題概要 × のマス目があり、そのうちの マスについては既に 以上 以下の数値が入れられている。残りの マスに 以上 以下の数値を入れる方法のうち どの行の和と、どの列の和をとっても、その一…

TopCoder SRM 309 D1H StoneGameStrategist

staircase nim の流れで 問題へのリンク 問題概要 個の石の山が左から順に一列に並んでいて、各山には 個の石が積まれている。初期状態では を満たしている。今先手と後手が交互に 石が 1 個以上ある好きな山を 1 つ選んで 何個かの石を取り去る ただし とい…

TCO 2018 Round 3B Med TestProctoring

楽しい!!!!!!!!!すごく勉強になったん!!!!! 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…

TopCoder SRM 735 D1M QuadraticIdentity

ちょうど中国剰余定理シリーズやっていたので、ピンポイントだったん。 SRM 735 DIV1 Medium QuadraticIdentity 問題概要 整数 が与えられる。 (mod. ) を満たすような < ) をすべて求め、そのサイズが 500 より大きい場合には 500 以下になるまで以下の操作…

TopCoder SRM 694 D1H SRMDiv0Easy

二段階単体法のデバッグに苦労しました。 問題概要 初期状態が全要素が 0 であるような N 次元ベクトルに対し、 以下のような Q 個の区間クエリを実施して得られる結果が 全要素が等しい N 次元ベクトルとなるようにしたい。区間クエリ i: 閉区間 [ L[i], R[…

TopCoder SRM 694 D1M DistinguishableSetDiv1

難しく考えすぎてしまった。 文字列問題をみてもひるまずに解けるようになりたい。 問題概要 m 文字からなる文字列が n 個与えられる。 {0, 1, 2, …, m-1} の部分集合 bit のうち、 どの 2 つの文字列を選んでも、それらの文字列の bit に対応する部分文字列…

TopCoder SRM 694 D1E TryShell

いい問題だった。 問題概要 0 以上 255 以下の整数が n 個与えられる。 この n 個の整数を 3 組に分ける方法のうち、各組の xor 和の総和が最大となるものを求めよ。(制約) ・3 解法 dp[ i+1 ][ j ][ k ] := i 番目までみたとき、二組の和がそれぞれ j, k の…