灰色diff
二次元配列の練習問題! 問題へのリンク 問題概要 整数 と、2 行 2 列からなる行列 が与えられるので、 を出力せよ。 解法 2 行 2 列の行列は、次のような 2 次元の配列で実装できる。 int A[2][2]; そうすると、 行目 列目の要素は、A[R][C] と表せる。 コ…
少し面白い問題! 問題へのリンク 問題概要 長さが 1, 2, 3 のいずれかの文字列 が与えられる。 を繰り返して得られる文字列であって、長さが 6 であるものを答えよ。 考えたこと 次のように考えれば良い。 の長さが 1 のとき: を 6 回繰り返す の長さが 2 …
上手に解釈して問題を解こう! 問題へのリンク 問題概要 0 と 1 のみからなる長さ 4 の文字列 が与えられる。この文字列は、4 マスからなる各マスに人がいるかどうかを表す。 はそのマスに人がいることを表し、 は人がいないことを表す。 今、人がみな右へ移…
文字列の末尾の文字を取得する方法を確認しておこう! 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の末尾の文字を出力せよ。 解法 C++ では、文字列 S の末尾の文字は S.back() によって取得できます。 別解 文字列 S の長さが であるとき、末尾…
パズルのような問題! 問題へのリンク 問題概要 0 以上 9 以下の 2 つの整数 が与えられる。 0 以上 9 以下の整数のうち、 とは異なるものを 1 つ求めよ。 考えたこと もし でなければ、0 を出力すれば事足りる。 もし であるならば、0 以外の数 (たとえば 1…
for 文を回しながら、隣接要素を見ていく練習をしよう! 問題へのリンク 問題概要 個の整数 が与えられる。 に対して、 の値を順に求めよ。 制約 考えたこと for 文を回しながら、隣の要素も同時に見ていくスキルを習得しよう! コード #include <bits/stdc++.h> using name</bits/stdc++.h>…
for 文の練習! 問題へのリンク 問題概要 個の整数 が与えられる。 これらのうち、 で割り切れるものについて、 で割った値を順に出力せよ。 考えたこと 入力を配列 (C++ ならば vector 型など) で受け取り、for 文を使って配列の各要素にアクセスしていこう…
ooxooxooxoox... を出力する問題 問題へのリンク 問題概要 髙橋君はサッカーの試合で 回ペナルティキックを蹴る。3 の倍数回目は失敗する。 回分のキックの結果を出力せよ。 解法 for 文を用いて、 について が 3 の倍数のとき:文字 'x' を出力 そうでない…
数学の部分を乗り越えることが難しいかもしれない。 問題へのリンク 問題概要 人 が、一対一の勝敗のつくゲームを何度か行った。 人の最初の持ち点は 0 点である。 各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減る。(持ち点が負になることもある…
ソートに関する練習問題! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらの数列の値はすべて互いに相異なる。 これらの 2 つの数列の各要素 について、次の値を求めよ。 2 つの数列を連結してできる長さ の数列を小さい順に並…
二次元配列の練習問題 問題へのリンク 問題概要 の形状に並べられた行列が与えられる。行列の各要素は 0 以上 26 以下の整数値である。 今、この行列の各要素に対応して 0 は文字 '.' に 1〜26 はそれに対応するアルファベット文字に 置き換えて得られる の…
回転寿司を題材にした、とても教育的な面白い問題! 問題へのリンク 問題概要 高橋君は料理を 皿分食べた。皿 の色は文字列 であった。 また、料理の価格は皿の色と対応し、各 について、色が文字列 の皿の料理は一皿 円である。 また、 のいずれとも異なる…
long long 型だとオーバーフローしてしまうので注意! unsigned long long 型なら大丈夫! 問題へのリンク 問題概要 0 と 1 からなる長さ 64 の数列 が与えられる。 の値を求めよ。 考えたこと 実は long long 型は、 以上 以下の整数しか表せない。今回扱う…
一見面倒そうに思える問題 問題へのリンク 問題概要 直線上に 7 点 A, B, C, D, E, F, G が下図のような間隔で並んでいる。 2 点を示すアルファベット が与えられるので、それらの間の距離を求めよ。 考えたこと 一見すごく面倒そうな問題だけど、工夫次第で…
ビンゴを題材とした問題。行・列・斜めを合わせて 個のラインがあるので、各ラインの空きマス数を管理しよう。 問題へのリンク 問題概要 のグリッドがあり、上から 行目、左から 列目のマスには整数 が書かれている。 今から ターンの穴あけをする。 ターン…
元ネタのあるシミュレーション問題 問題へのリンク 問題概要 高橋君は英小文字からなる文字列 をキーボードで入力しようとしました。 高橋君は誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキー…
実装問題! 問題へのリンク 問題概要 のグリッドがあって、各マスは白色または黒色に塗られている。今、「白色のマスを選んで黒色に塗る」という操作を高々 2 回まで実施できる。 操作後に、縦・横・斜めのいずれかに連続して 6 個のマスが黒色になるように…
「グラフ」の基礎になるような、配列上のシミュレーションの問題。 問題へのリンク 問題概要 整数 が与えられる。 このとき、ボタンを押すと、画面の数値 () が に変わる。 最初の数値が 0 であるとき、ボタンを 3 回押すと、どんな数値に変わるか? 考えた…
ビット全探索の要領で列挙できる。だが、実は、部分集合列挙には専用の書き方も存在する! 問題へのリンク 問題概要 非負整数 が与えられる。次の条件を満たす非負整数 を昇順にすべて出力せよ。 と をともに二進法で表すとき、 において値が 1 である桁につ…
ビット全探索の典型問題! 問題へのリンク 問題概要 ポップコーンには 種類の味 がある。 一方、ポップコーンを得る 個の店 がある。各店 でどの味のポップコーンを売っているかを表す文字列 が与えられる。文字 が 'o' であるとき、店 で味 を売っているこ…
面白い問題! 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…
めっちゃ面白い問題!! 実はよく似た類題として次の問題がある! atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …
「2 つの区間の交差している部分の長さ」を求める問題は典型。それが 3 次元になってもやることは一緒。 問題へのリンク 問題概要 3 次元空間内の直方体であって、2 点 を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なもの…
for 文の練習問題! 問題へのリンク 問題概要 個の商品があって、それぞれ価格は 円である。これらをすべて購入する。 ただし、最高価格のものは半額となる。このとき、支払い金額の総和を求めよ。 制約 は偶数 解法 について、 総和を 最大値を としよう。…
for 文の練習問題。 問題へのリンク 問題概要 長さ の整数列 が与えられる。 この数列の 番目の要素の直後に値 を挿入して得られる数列を出力せよ。 解法 (1):関数 erase() を利用する C++ では、vector 型変数 A に対して、 番目に値 を挿入する処理は A.i…
この手のシミュレーションになれることはとても大事! 問題へのリンク 問題概要 あるチケット売り場は、待合行列がなければ、来た人の受付に 秒かかる。 人の人 は、それぞれ時刻 に到着する。まだ受付されていない人がいる場合は後ろに並ぶ。 人 がそれぞれ…
条件を上手に言い換えて、探索しやすい感じにしよう! 問題へのリンク 問題概要 をちょうど 2 個ずつ含む数列 が与えられる。 次の条件を満たす の個数を求めよ。 「数列中の、値が であるような 2 つの要素は、ちょうど 1 個の他の要素を挟む」 制約 考えた…
問題文の理解が大変かもしれない。 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。次の条件を満たす 2 角整数 () が存在しるかどうかを判定せよ。 「文字列 を 文字ごとに分割したとき、各分割された文字列の 文字目を連結して得られる文字…
if 文の練習! 問題へのリンク 問題概要 2 つの文字列 が与えられる。 = "AtCoder" かつ = "Land" であるかを判定せよ。 解法 = "AtCoder" であるかどうかは if (S == "AtCoder") によって判定できる。 についても同様である。 よって、 = "AtCoder" かつ = …
基本的な for 文の問題 問題へのリンク 問題概要 個の文字列が与えられる。各文字列は "Takahashi" か "Aoki" のいずれかである。 "Takahashi" が何個あるかを数えよ。 解法 個の文字列を順に受け取って、"Takahashi" と一致するものを数えれば良い。 #inclu…