2020-01-01から1ヶ月間の記事一覧
バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう... 問題へのリンク 問題概要 要素の数列 が与えられる。 の順列 に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応…
すごく詰め切るのに時間かかった 問題へのリンク 問題概要 (意訳) 二次元平面上に 個の座標 (格子点) が与えられる。正の整数 が与えられる。 まず、各座標について「 座標を だけ増減する」「 座標を だけ増減する」という操作を好きなだけ繰り返す。ただし…
差分更新系の代表的問題。でも頭がごっちゃになって大変だった。 問題へのリンク 問題概要 'D', 'M', 'C' からなる長さ の文字列 と正の整数 が与えられる。 の添字 であって S[ ] = 'D' S[ ] = 'M' S[ ] = 'C' を満たすものの個数を求めよ (というクエリに …
最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…
sky さんの Monotone Minimma の例題!!! 練習として解いてみた。 問題へのリンク 問題概要 (意訳) 個の値の組 , が与えられる。 で であり、 は狭義単調増加、 は狭義単調減少である。 を適切に定めたときのスコアが、 で与えられる。スコアの最小値を求…
伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…
0. はじめに bit 全探索は、世の中で「AtCoder 温室育ちだと弱い」と言われるタイプの問題の代表かもしれません。何も考えずに思考停止して全探索すればよいのですが、ちょっと実装が重たい傾向にあって、書き切るのが大変という感じです。difficulty を見て…
二分探索の教育的問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき を満たす最大の正の整数 を求めよ。 制約 考えたこと わけわからない式だし、二分探索に決まってるやろ!!!という雰囲気があ…
C 問題で整数系のアルゴリズムを確認する問題を出すの良さそうやね。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 以上の最小の素数を求めよ。 制約 素数判定 整数 が素数かどうかを判定するのは、整数論的アルゴリズムで最初くらいに学ぶものです…