バケットの練習を兼ねた、インタラクティブ問題！ 問題へのリンク 問題概要（インタラクティブ） 最初に、正の整数 が与えられて、ゲームをする。あなたは高橋君で先手である。相手は青木君で後手である。 交互に、1 以上 以下の整数を言っていく。ただし、…

バケットを用いた集計処理や、Greedy の練習！ 問題へのリンク 問題概要 個の整数 が与えられる。いくつかの整数を他の好きな整数に書き換えることで、数列に含まれる整数値の種類数が 以下となるようにしたい。 書き換える整数の個数の最小値を求めよ。 制…

B 問題としては難しい！ 今風にいうと、Functional Graph のシミュレーション！ 問題へのリンク 問題概要 個のボタンがある。ボタン が光っているときにそのボタンを押すと、ボタン の明かりが消え、その後ボタン が光る（ であることもある）。 最初、ボタ…

いい感じの教育的典型問題。いもす法したあとに累積和する！ 問題へのリンク 問題概要 個のマス がある。 個の区間があって、それぞれマス からマス までを連続して覆っている。 個の区間によって一回以上被覆されるマスの集合を とする。 各区間について、…

とても教育的な易しい問題！ 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。 の文字がすべて互いに相異なるかどうかを判定せよ。 解法 (1)：多重 for 文 最も素朴な方法は、 から 2 文字を選ぶ方法をすべて試して、「それらが異なっている…

二次元グリッド上のシミュレーション問題！ 問題へのリンク 問題概要 のグリッドが与えられる。各マスは '.'：通路マス '#'：壁マス '@'：アイテムマス のいずれかである。最初、マス にいる。 今、グリッド上で文字列 に示す移動をする（U, D, L, R のいず…

条件を上手に言い換えよう！ 問題へのリンク 問題概要 個の整数 が与えられる。 が平方数 という条件を満たすような組 の個数を求めよ。 制約 考えたこと これは「条件の言い換え」を頑張る問題。「 が平方数」という条件を扱いやすいように言い換えよう。こ…

ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…

これ結構難しくて、嵌まる人は嵌まってしまうと思う！！ 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき：ポーション が現れる それを拾うかどう…

スタックによるシミュレーション問題！ 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…

集計処理の応用問題 問題へのリンク 問題概要 一般に、文字列 からいくつかの文字を抜き出して、それを並び替えることによって文字列 を作れるとき、 から を作れるという。 英小文字からなる 個の文字列 が与えられる。 のいずれからも作れる文字列 のうち…

グラフの基本問題！ 問題へのリンク 問題概要 の人 がいる。 組の友達関係があって、 組目の友達は人 と である。 人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。 制約 解法 この問題はグラフの練習問題といえる。グラ…

すごろくを題材にした問題。すごろくの各マスには「oo マス進む」などの指示がある。これを上手に管理しよう。 問題へのリンク 問題概要 マス からなる双六が与えられる。マス 1 がスタート、マス 以上がゴールである。 回サイコロを振って、 回目には目 だ…

バケットを活用する練習問題！ 問題へのリンク 問題概要 AtCoder 王国には 家がある。どこかの家で順に 人の赤子が生まれた。 人目の赤子は家 で生まれ、性別は （'M' または 'F'）であった。 各赤子が長男であるかどうかを判定せよ。 制約 考えたこと 人目…

ちょっと実装が大変なので、頑張って実装しよう！ 問題へのリンク 問題概要 太郎君と花子さんが大富豪を模したゲームをする。 の書かれたカードを、 枚ずつ、太郎君と花子さんに配る。太郎君に配られたカードに書かれた 個の数値が与えられる。2 人で次のよ…

これも色んな解法がある！ 問題へのリンク 問題概要 英小文字からなる 3 文字以上 100 文字以下の文字列 が与えられる。 はある 1 文字を除いて全て同じ文字で構成されています。その異なる文字があるのは何文字目か？ 制約 解法 (1)：全探索 大抵の問題は、…

少し数学チックな問題！ 問題へのリンク 問題概要 二次元の座標平面上に 個の点がある。点 の座標は である。 これら 個の点から 4 個を選ぶ。選んだ 4 点が正方形の頂点となる場合についての、正方形の面積の最大値を答えよ。 制約 考えたこと であるような…

これ結構難しい気がする！ グラフの問題の一種。 問題へのリンク 問題概要 人 がいる。高橋君（ 人のいずれとも異なる）は、自分の秘密を、この中の人 に知られてしまった。 一般に、人 は新たに秘密を知ったときには、人 にも伝えてしまう。 高橋君の秘密は…

この手の問題は最初にソートすると考えやすいことが多い。 問題へのリンク 問題概要 5 枚のカードには数 が書かれている。これがフルハウスであるかを判定せよ。 なお、5 つの数がフルハウスであるとは、同じ数が書かれたカード 3 枚と、別の同じ数が書かれ…

よくある「集計処理」の問題！ 問題へのリンク 問題概要 10 個の数字 0〜9 のうちから 1 つを除外した 9 個の数字からなる文字列 が与えられる。 10 個の数字 0〜9 のうち、この文字列に含まれない数字を答えよ。 考えたこと この手の問題では、次のような配…

集計処理系の良問！ 問題へのリンク 問題概要 英小文字からなる文字列 について、どの英小文字も登場回数が偶数回であるかどうかを判定せよ。 制約 解法 (1)：各文字について登場回数を見ていく まずは愚直な解法を考えよう。文字 = 'a', 'b', ..., 'z' につ…

集計処理を練習しよう！ 問題へのリンク 問題概要 以上 以下の整数からなる、長さ の数列 が与えられる。 長さ の新たな数列 を次のように定義する。 各 に対して、 を、 を満たす の個数 の最大値を求めよ。 制約 解法 問題の意味を解釈するのが難しいかも…

このような問題を解くためにも、「バケット」を習得しよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 こっらの数列の双方に登場する数をすべて昇順で出力せよ。 制約 解法 (1)：1 から 100 までの数を順に調べる 制約を見よう…

集計処理の面白い問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 に出現する整数のうち、出現回数が最小である整数を出力せよ。そのようなものが複数あるときは、そのうちの最小の整数を出力せよ。 制約 解法 このような出現頻度に関する問題で…

「検索」をしながらのシミュレーション！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 回のゲームをする。最初の得点は 0 点である。 回目のゲームでは、得点が 点増加する。ただし、増加したあとの得点が、もし数列 の中に含まれ…

バケットや集計処理の基本問題！ 問題へのリンク 問題概要 を 2 個ずつ集めてできる 個の整数から、1 個の整数を除外した。 そうした 個の整数を並べてできる数列 が与えられる。 最初に除外した整数の値を答えよ。 制約 解法 このくらいの難易度の問題から…

一見面倒そうに思える問題 問題へのリンク 問題概要 直線上に 7 点 A, B, C, D, E, F, G が下図のような間隔で並んでいる。 2 点を示すアルファベット が与えられるので、それらの間の距離を求めよ。 考えたこと 一見すごく面倒そうな問題だけど、工夫次第で…

ビンゴを題材とした問題。行・列・斜めを合わせて 個のラインがあるので、各ラインの空きマス数を管理しよう。 問題へのリンク 問題概要 のグリッドがあり、上から 行目、左から 列目のマスには整数 が書かれている。 今から ターンの穴あけをする。 ターン…

面白い問題！ 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…

二次元いもす法の練習問題 問題へのリンク 問題概要 二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。 紙に覆われている部分の面積を求めよ。 制約 考えたこと 二次元いもす法の練習。 github.com コード #incl…