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

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

周期性に着目する

AtCoder ABC 179 E - Sequence Sum (500 点)

この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…

AtCoder ABC 175 D - Moving Piece (400 点)

異様に難しかった!! 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…

AtCoder ABC 167 D - Teleporter (400 点)

回操作した後の結果を求めよ (ただし がめちゃくちゃ大きい) という問題は、 同じ処理の繰り返しとなっているところを見抜く ダブリングする というパターンが多いと思われる。 問題へのリンク 問題概要 個の町 がある。町 からは、町 へテレポートできる。…

AtCoder ABC 165 D - Floor Function (400 点)

気づけば一発系。ただし、数式の見た目がエグく見えてしまうかもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数 に対する - の値の最大値を求めよ。 制約 考えたこと 全探索すれば だけど、それでは間に合わない。さて、式の…

AtCoder AGC 003 E - Sequential operations on Sequence (1400 点)

この頃、数列を繰り返すのが流行ってたのかな 問題へのリンク 問題概要 長さ の恒等数列 () が与えられる。この数列に以下の操作を合計で 回行う。 番目の操作は、パラメータ であらわされ、以下のように行われる。 現在の数列を無限回繰り返した数列の先頭 …

AtCoder ARC 071 F - Infinite Sequence (1000 点)

ダブルカウントに気をつければ難しくない。現代なら 700 点かもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数からなる無限数列 のうち 任意の について であるとき、 から連続する 個は同じ値である を満たすものの個数を 1…

AtCoder ARC 064 F - Rotated Palindromes (1000 点)

約数系包除。かなり教育的要素の多い問題だと思った!!!!! 操作によって何通りできるのかを問う問題の取り組み方 約数系包除の考え方 問題へのリンク 問題概要 以上 以下の整数からなる数列のうち、以下のようにしてつくられるものは何通りあるか、10000…

AOJ 3045 Painting (ACPC 2018 day2 G)

コンテスト本番、つたじぇーが頑張って通してくれた!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。初期状態では の要素は全て 0 である。加えて、 個の整数のペア()が与えられる。各ペアに対し以下の操作を行い、最終的な数列 を出力せよ。 各 …

AtCoder ARC 060 F - 最良表現 (900 点)

今回は Suffix Array でやってみたけど、ローリングハッシュとか、KMP とか、Z-Algorithm とか、色んな方法があるみたいなので追々やってみたい。 → やってみた (3/14) 問題へのリンク 問題概要 文字列 がよい文字列であるとは「いかなる文字列 および 2 以…

AtCoder ABC 106 C - To Infinity (300 点)

十分多い回数重ねるとなにかが収束する系はよく見るん 問題へのリンク 問題概要 (ABC 106 C) 1 から 9 までの数字からなる文字列 S がある。以下の操作を 5000 兆回行う: 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666…

AtCoder AGC 013 C - Ants on a Circle (700 点)

蟻さんぐるぐるなのん 問題へのリンク 問題概要 (AGC 013 C) 長さ の円周上を 匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。 匹の蟻は最初 の地点にいた。どの蟻が最初に…

AtCoder AGC 026 B - rng_10s (600 点)

あーーーーーー、これは大好物系なん!!!!! 本番でやってみたかったん!!!!! 問題へのリンク 問題概要 (AGC 026 B) 整数 があたえられる。 最初は在庫に 個あって、 毎日 個ずつ消費される その日の最後に 個以下しか残っていなかったら 個補充され…