AtCoder
場からカードを手札に入れない方が良い場合があるの、すごい！ あと、局面状態を数値情報にエンコードするかを迷ったけど、エンコードしなくても通った。 問題へのリンク 問題概要 はじめ、高橋君は整数 の書かれた 枚のカードを持っていて、青木君は整数 の…
公式解説の方がシンプルだった。 問題へのリンク 問題概要 の順列 と、整数 が与えられる。 の連続する 個の要素からなる区間（ 通りある）をランダムに選び、さらにその区間をランダムシャッフルする。 最終的な順列の転倒数の期待値を mod 998244353 で求…
遅延評価セグメント木と、その max_right, min_left で殴った！ 問題へのリンク 問題概要 マス が一列に並んでいて、それぞれ色 で塗られている。次の 回のクエリに答えよ。 クエリタイプ 1：マス と色 が指定されるので、マス から始めて「いまいるマスと同…
実験していくうちにシンプルな構造がわかった。 問題へのリンク 問題概要 英文字からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を 回行ってできる文字列を考える。 【操作】 文字列 に対して、英小文字と英大文字を入れ替えてできる文字…
ランレングス圧縮で解いた 問題へのリンク 問題概要 0 と 1 からなる長さ の文字列 が与えられる。この文字列の中での「1 の塊」のうち、左から 番目のものを、 番目のものの右に移動させよ。 例："010011100011001" → "010011111000001" 制約 考えたこと ま…
初歩的な構文解析問題 問題へのリンク 問題概要 "|---|-|----|-|-----|" のような、文字 '-' を文字 '|' で separate された文字列 が与えられる。 各 '-' 区間の '-' の個数を順に出力せよ。 制約 考えたこと ここでは for 文で解いてみよう。次の変数を管…
ソートが使えるなら、それが楽だと思う 問題へのリンク 問題概要 6 桁の正の整数 が与えられる。 が次の条件を満たすかどうかを判定せよ。 1 をちょうど 1 個含む 2 をちょうど 2 個含む 3 をちょうど 3 個含む 解法 (1)：1, 2, 3 の個数を数える方法 for 文…
久しぶりに高難易度問題を解いてみた！ 問題へのリンク 問題概要 各マスの値が 0 または 1 である グリッドを考える。 グリッド のマス が「固定されている」とは、次の条件を満たすすべての グリッドについて、マス の値が一意に決まることをいう。 すべて…
「主客転倒・寄与分解」の典型問題！ 問題へのリンク 問題概要 1 から 9 までの数字からなる 桁の整数値 が与えられる。 この整数値の連続する区間を取り出してできる整数値の総和を求めよ。（998244353 で割らない。） 制約 考えたこと この手の問題では、 …
「全体に足す」のは難しいから、足す値を別途持っておくというスキル！！！ 問題へのリンク 問題概要 以下の 個のクエリに答えよ。 クエリタイプ 1：新たに要素 0 を挿入する（重複もあり） クエリタイプ 2：すでに挿入されているすべての要素に を足す クエ…
これはややこしい！ 問題へのリンク 問題概要 マス が一列に並んでいる。最初、 個のマスに石が入っており、マス には 個の石が入っている。あなたは以下の操作を好きな回数行うことができる。 「マス に石があるとき、マス からマス へと石を 1 つ移動させ…
チェスを題材とした問題 問題へのリンク 問題概要 8 x 8 のチェス盤のいくつかのマスにルーク（上下左右にどこまでも行く）が置かれている。 これらのどのルークにも取られないマスの個数を求めよ。 考えたこと 8 x 8 の盤面に対応する二次元配列を用意して…
ランレングス圧縮！ 問題へのリンク 問題概要 文字 'O', 'X' からなる長さ の文字列 が与えられる。 「'O' のみからなる連続 個の文字をすべて 'X' に書き換える」という操作を最大で何回行えるか？ 制約 考えたこと ランレングス圧縮が有効な問題。ランレン…
3 つのものを扱う系の問題、昔はよく出ていた。 問題へのリンク 問題概要 各桁の値が 1〜9 である 3 桁の整数 abc が与えられる。 bca と cab を出力せよ。 考えたこと 整数値で受け取るよりは、3 つの char 型変数 a, b, c で受け取るのが楽。 そうすると、…
座標ごとに情報を整理するのは頻出！ 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている（各人が左右どちらを向いているかは文字列 で与えられる）。 各人が、その位置から、向いている方向に向かっ…
意外と整理するのが大変だと思う。map を使って整理しようとするのも自然だが、もうちょっと簡単に解くことを考えよう。 問題へのリンク 問題概要 文字列を投稿すると得点が与えられるコンテストに、 個の文字列 がこの順に投稿され、それぞれ 点が与えられ…
SNS を題材にした set の練習問題 問題へのリンク 問題概要 人から SNS について、次の 個のクエリに答えよ（初期状態では全員が誰もフォローしていない）。 クエリタイプ 1：人 が人 をフォローする（フォロー済みの場合は何もしない） クエリタイプ 2：人 …
ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…
区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題！ 問題へのリンク 問題概要 数列 について、連続する 個の要素の種類数の最大値を答えよ。 制約 考えたこと 数列の幅 の区間をすべて調べるには、次の…
この問題は、for 文でも解けるし、map でも解ける。ここでは map で解いてみよう。 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 これに対して文字列を考えて、その文字列に対するスコアは ( に含まれている分の個数) - ( に含まれて…
if 文を並べてもいいし、map を使ってもよさそう。 問題へのリンク 問題概要 文字列 が与えられる。 の各文字に対して、 O → 0 D → 0 I → 1 Z → 2 S → 5 B → 8 それ以外 → そのまま という変換をして得られる文字列を答えよ。 コード (1)：if 文 if 文を使っ…
連想配列の練習問題！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。この数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、整数列を順に見ていったときの「 個目の値 の要素」の index を答えよ（存在しない場合は -1）…
辞書順最小と言われたら......！！ 問題へのリンク 問題概要 文字 'd', 'p' からなる長さ の文字列 が与えられる。 この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。 こうしてできる文字列のうち…
制約が小さいので for 文だけでも解けるし、map などを使うともっと楽になる。 問題へのリンク 問題概要 個の文字列 が与えられる。 登場回数の最も多い文字列を答えよ（タイがある場合はどれを答えても良い）。 制約 考えたこと 次の連想配列を用いて解いた…
連想配列が有効活用できる問題 問題へのリンク 問題概要 個の文字列 がある。 登場回数の最も多い文字列を、辞書順に出力せよ。 制約 考えたこと 各文字列がそれぞれ何個あるのかを求めたい。そこで、次のような配列を作りたい。 nums[str]：文字列 str の登…
set の練習！ 問題へのリンク 問題概要 二次元平面上に高橋君がいる。高橋君は原点から移動を 回行った。 回の移動は長さ の文字列で表される。各文字は L（左へ移動）、R（右へ移動）、U（上へ移動）、D（下へ移動）のいずれかである。 高橋君が同じ座標に…
連想配列（辞書）の練習問題！ 問題へのリンク 問題概要 文字列 が与えられる。 各 に対して、 となる が存在しない場合は をそのまま出力せよ となる が存在する場合は、その個数を としたとき、 に "(k)" を付して出力せよ 制約 考えたこと 問題文で言われ…
ちょっと整理が大変な複雑な問題。 問題へのリンク 問題概要 ルーレットによって 0 から 36 までのいずれかの整数が出される。 人 はどの整数が出されるかを賭けた。人 は 個の整数 にかけた。 実際に出た整数は であった。 に賭けていた人のうち、賭けた整…
連想配列で集計するといい感じに解ける！ 問題へのリンク 問題概要 枚の靴下があって、靴下 の色は という整数値で表される。 色の等しい靴下をペアにするとき、最大で何ペア作れるか？ 制約 考えたこと 次のように考えたい。 色ごとに靴下が何個あるかを整…
すごく数学的な問題 問題へのリンク 問題概要 縦、横、高さの総和が であるような直方体の体積の最大値を求めよ。 制約 考えたこと 縦、横、高さの長さを としよう。このとき、次の問題になる。 のとき、 の最大値を求めよ この手の問題では、 のとき最大に…
