AtCoder300点
種類数に関する面白い問題！ 問題へのリンク 問題概要 2 つの文字列 は、 である を左右反転してできる文字列 について、 である といういずれかの条件を満たすとき、似ているとみなす。 与えられた 個の文字列 について、似ている文字列は同一視することに…
バケットの練習を兼ねた、インタラクティブ問題！ 問題へのリンク 問題概要（インタラクティブ） 最初に、正の整数 が与えられて、ゲームをする。あなたは高橋君で先手である。相手は青木君で後手である。 交互に、1 以上 以下の整数を言っていく。ただし、…
「変数を固定する考え方」と「set の活用」を組み合わせる練習問題！ 問題へのリンク 問題概要 整数 と、 個の整数 が与えられる。 を満たす [tex i, j] ( でもよい) が存在するかを判定せよ。 制約 考えたこと この問題のように、 という 2 つの変数を考え…
set の練習問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 重複を除くと何種類の文字列があるでしょうか。 制約 文字列長さは 10 以下 考えたこと 重複を除外したいとなったら、集合型（C++ ならば set 型）が使える！ 具体的には、set<string> 型の変数</string>…
set の練習問題！ 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 について、 の中に と一致するものがあるかどうかを判定せよ。 制約 各文字列の長さは 10 以下 考えたこと set 型のよい練習問題。 を格納する集合（C++ であれば set<string> </string>…
いろんな解法がある。ここでは、ソートで解いてみよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 各数列から要素 を選んだときの差 の最小値を求めよ。 制約 考えたこと 本当にいろいろな解き方がある。その中でも易しいのは、…
Greedy の基本でもある。 問題へのリンク 問題概要 駅 があって、駅 から駅 へと、時刻 以降、 秒ごとに発車する列車があって、移動に 秒かかる。他の駅間を移動する列車はない。また、 は の倍数であることが保証される。 各 に対して、駅 を時刻 0 に出発…
初歩的な Greedy の問題と言える。 問題へのリンク 問題概要 以上 以下の整数からなる数列 であって、 は で割り切れる という条件を満たすものを考える。そのような数列の長さの最大値を求めよ。 制約 考えたこと 基本的には、なるべく小さい値でスタートし…
バケットを用いた集計処理や、Greedy の練習！ 問題へのリンク 問題概要 個の整数 が与えられる。いくつかの整数を他の好きな整数に書き換えることで、数列に含まれる整数値の種類数が 以下となるようにしたい。 書き換える整数の個数の最小値を求めよ。 制…
ビット全探索の練習問題。少し問題内容を理解するのに手こずるかもしれない。 問題へのリンク 問題概要 すでに 個の店が出店している商店街で、新たに店を開こうとしている。 どの店についても 10 個の時間帯があり、それぞれについて open・close を選ぶこ…
ABC-C の最易候補！ ビット全探索でもいいが、8 通りだけなので if 文の羅列でも OK。 問題へのリンク 問題概要 4 つの整数 が与えられる。 □ □ □ = 7 となるように、□ に + または - を入れよ。 制約 考えたこと □ は 3 個ある。それぞれに「＋」と「－」の…
面白かった！ 問題へのリンク 問題概要 英小文字および文字 '?' からなる文字列 が与えられる。 の各 '?' を英小文字に置き換えてできる文字列のうち、次の条件を満たす辞書順最小のものを求めよ。 (条件) 文字列 を連続する部分文字列として含む 制約 考え…
日頃から「まずは全探索！」という意識があれば、この手の問題は全探索でできると気づけるはず！ 問題へのリンク 問題概要 ビーカーに対して、次の 4 種類の操作を好きな順序で好きな回数だけ実行する。 ビーカーに g の水を入れる ビーカーに g の水を入れ…
色々な解法があるが、set を使うのが楽。set のよい練習問題とも言える。 問題へのリンク 問題概要 最初何も書いていない黒板がある。次の 回の操作を行った。 回目の操作では、整数 を考える 黒板に が書かれていない場合は、新たに を黒板に書く 黒板に が…
長さが大きい順に処理していこう！ 問題へのリンク 問題概要 長さが の棒がある。 これらの棒を 4 個選んで長方形を作りたい。作れる長方形の面積の最大値を求めよ。長方形を作れない場合は 0 と答えよ。 制約 考えたこと できるだけ大きい長さの棒を使いた…
最小公倍数を求めよう！ 問題へのリンク 問題概要 台の時計があり、時計 の針はちょうど 秒で時計盤を 1 周する。 最初、全ての時計の針は真っ直ぐ上に向いており、止まっている。イルカは、全ての時計の針を同時に動かし始めた。再び、全ての時計の針が真っ…
計算量の意識が必要になる良問！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。これを左右に 2 つに分ける（左右ともに 1 個以上はとる）。 左側の要素の総和を 、右側の要素の総和を とするとき、 の最小値を求めよ。 制約 考えたこと もし…
完全に言われた通りに実装してしまうと、 の計算量となって TLE してしまうので、工夫しよう！ 問題へのリンク 問題概要 空の配列に対して、以下の操作を 回行う。 回目の操作では 配列の末尾に値 を挿入する 配列全体を reverse する を行う。 回操作後の配…
数学 IA でもありがちな問題！ 問題へのリンク 問題概要 匹の犬 と、 引の猿 を一列に並べる。 犬同士・猿同士がそれぞれ隣り合わないように並べる方法の数を 1000000007 で割った余りを求めよ。 制約 考えたこと 実は、 や の場合は、条件を満たすように並…
面白い問題。最近はこういうの、あまり見ないかもしれない。 問題へのリンク 問題概要 個の正の整数 が与えられる。 これらからいくつか選んで総和をとる。ただし、その値が 10 の倍数である場合には、その値は 0 になってしまう。 この値の最大値を求めよ。…
すごく面白い問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。 制約 考えたこと まずは、問題の条件をわかりやすく…
連想配列の良い練習問題！ 問題へのリンク 問題概要 正の整数からなる数列が良い数列であるとは、数列に含まれる任意の整数値 について、数列中に がちょうど 個含まれていることをいう。 与えられた数列 に対して、いくつかの要素を削除することで、よい数…
ランレングス圧縮で解いた 問題へのリンク 問題概要 0 と 1 からなる長さ の文字列 が与えられる。この文字列の中での「1 の塊」のうち、左から 番目のものを、 番目のものの右に移動させよ。 例："010011100011001" → "010011111000001" 制約 考えたこと ま…
これはややこしい！ 問題へのリンク 問題概要 マス が一列に並んでいる。最初、 個のマスに石が入っており、マス には 個の石が入っている。あなたは以下の操作を好きな回数行うことができる。 「マス に石があるとき、マス からマス へと石を 1 つ移動させ…
座標ごとに情報を整理するのは頻出！ 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている（各人が左右どちらを向いているかは文字列 で与えられる）。 各人が、その位置から、向いている方向に向かっ…
意外と整理するのが大変だと思う。map を使って整理しようとするのも自然だが、もうちょっと簡単に解くことを考えよう。 問題へのリンク 問題概要 文字列を投稿すると得点が与えられるコンテストに、 個の文字列 がこの順に投稿され、それぞれ 点が与えられ…
SNS を題材にした set の練習問題 問題へのリンク 問題概要 人から SNS について、次の 個のクエリに答えよ（初期状態では全員が誰もフォローしていない）。 クエリタイプ 1：人 が人 をフォローする（フォロー済みの場合は何もしない） クエリタイプ 2：人 …
ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…
区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題！ 問題へのリンク 問題概要 数列 について、連続する 個の要素の種類数の最大値を答えよ。 制約 考えたこと 数列の幅 の区間をすべて調べるには、次の…
連想配列の練習問題！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。この数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、整数列を順に見ていったときの「 個目の値 の要素」の index を答えよ（存在しない場合は -1）…
