2020-03-01から1ヶ月間の記事一覧
まさか残り 25 分で通し切れるとは思わなかった! 問題へのリンク 問題概要 長さ の '0' と '1' のみからなる文字列 が与えられる。以下の 個のクエリに答えよ 各クエリは left, right, len からなる 部分文字列 A = S[left : left + len], B = S[right: rig…
セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい! 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…
似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題! 問題へのリンク 問題概要 重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通…
面白かった 問題へのリンク 問題概要 要素の数列 が与えられる。以下の条件を満たすような部分数列のうち、要素和の最大値を求めよ。 抜き出した数列のどの 2 項についても「値の差分」と「index の差分」とが等しい 制約 考えたこと たとえば の場合は、こ…
とても教育的な Union-Find!!! 問題へのリンク 問題概要 人がいて、 組の友達関係と、 組のブロック関係がある (いずれも双方向的)。 各人について、 直接的な友達関係ではない ブロック関係でもない 友達の友達の...とたどっていくと到着できる ような人…
全探索した! 整数を string 型にするのに手こずってしまった。 問題へのリンク 問題概要 以下の条件を満たす整数があれば、それを出力し、存在しなければ -1 を出力せよ。 ちょうど 桁である 左から数えて 桁目は である。() 制約 考えたこと 存在しない場…
12 が 4 の倍数で、112 が 8 の倍数だから、1112 が 16 の倍数なんじゃないの...と迷走したりしていた。 問題へのリンク 問題概要 以下の条件を満たす整数 を 1 つ求めよ (というクエリに 回答えよ) 桁の整数である どの位の値も 0 ではない 各桁の話を とし…
面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…
面白かった。セグ木にこういうの乗っけるの楽しい! 問題へのリンク 問題概要 の盤面の各マスに整数値が書かれている。このマスに対して、適切に を決めて、 盤面の 0 行目の区間 の総和 盤面の 1 行目の区間 の総和 盤面の 2 行目の区間 の総和 盤面の 3 行…