パリティ
連想配列で集計するといい感じに解ける！ 問題へのリンク 問題概要 枚の靴下があって、靴下 の色は という整数値で表される。 色の等しい靴下をペアにするとき、最大で何ペア作れるか？ 制約 考えたこと 次のように考えたい。 色ごとに靴下が何個あるかを整…
ちょっとした算数的な考え方が必要になる問題 問題へのリンク 問題概要 JOI 君は以下の行動を行動 A → 行動 B → 行動 A → ⋯ のように交互に繰り返す。 行動 A：3m 前に進む 行動 B：2m 後ろに戻る 行動を合わせて 回行うとき、何m進むか？ 解法 このような問…
偶数と奇数に関する理解も問われる問題。 問題へのリンク 問題概要 2 つの整数 が与えられる。 「 を並び替えると等差数列をなす」 という条件をみたすような整数 が何通りあるか求めよ。 制約 解法 (1)：数学的に解く まず、 の大小関係で場合分けして考え…
for 文のループカウンタ が偶数か奇数かに応じて処理を変える問題！ 問題へのリンク 問題概要 長さが奇数 の文字列 が与えられる。 この文字列に対して、次の操作をすることで、"IOIOIO...OI" というように "I" と "O" を繰り返す文字列にしたい。操作回数の…
偶数か奇数かを判定する問題！ 問題へのリンク 問題概要 高橋君の今日の状態は "White" である。 毎日 "White" と "Black" が入れ替わる。 日後の状態を答えよ。 解法 が偶数ならば、"White" が奇数ならば、"Black" である。 #include <bits/stdc++.h> using namespace std;</bits/stdc++.h>…
nC2 系の問題は ABC-D などで頻出だが、その練習ができる問題！ 問題へのリンク 問題概要 偶数の書かれたボールが 個 奇数の書かれたボールが 個 あります。これら 個のボールから 2 個選んで、書かれた数の和をとります。 この和が偶数になるような選び方は…
この切り上げ処理はぜひ憶えておこう！ 問題へのリンク 問題概要 高橋君は、全 ページから成る書類を両面印刷する。両面印刷では、1 枚の紙に 2 ページ分のデータを印刷することができる。 最小で何枚の紙が必要か求めよ。 解法 が偶数のときは、 は 2 で割…
いい感じの複合問題。この時期の ABC-A としては少し難しめ。 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数をランダムに選ぶとき、それが奇数である確率を求めよ。 解法 以上 以下の 個の整数のうち、奇数の個数を とすると、求める確…
これは難しい！ 問題へのリンク 問題概要 2 個の整数 が与えられる。 を満たすような整数 が存在すればそれを答えて、存在しない場合には "IMPOSSIBLE" と答えよ。 解法 これは難しい。結論から言えば、 は整数でなくてもよいならば、 の平均値 となる。下図…
天才構築ゲー。これ完全自力で一発 AC できて嬉しかった！！ 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。 頂点がすべて格子点であり、座標値は 以上 以下である すべて…
慎重に解いた。ノーペナで解けたのは収穫。 問題へのリンク 問題概要 のグリッドに、以下の条件を満たすように 個のルークと 個のポーンを配置することが可能かどうかを判定せよ (ルークとポーンを合わせて駒と呼ぶ)。 どのルークについても、それと同じ行・…
意外と問題文が読みにくい気もする。 問題へのリンク 問題概要 電車とバスを乗り継いで目的地にいきます。電車の運賃は 円、バスの運賃は 円でした。 ただし、バスの運賃が半額になる特別券を持っていたので使用しました。合計料金はいくらだったでしょうか…
パリティの問題。ここのところ、算数や数学の問題が続いている。 問題へのリンク 問題概要 1 以上 3 以下の整数 が与えられる。 が奇数 となるような 1 以上 3 以下の整数 が存在するかどうかを判定せよ。 解法 一般に、かけ算をするとき 偶数が 1 個でも含…
「場合の数」の問題！ 問題へのリンク 問題概要 1 以上 以下の正の整数から、偶数と奇数ひとつずつの組を選ぶ方法の個数を求めてください。 なお、選ぶ順番は考慮しません。 解法 まず、1 以上 以下の整数のうち、偶数の個数は K / 2 個である。よって奇数の…
整数問題！ 問題へのリンク 問題概要 整数 が与えられる。 と の最小公倍数を求めよ。 解法 一般に最小公倍数を求める方法としてはユークリッドの互助法が知られている。しかし、今回は次のように簡単に考えられる。 が 2 の倍数のとき：最小公倍数は が 2 …
ABS に採用した問題！ 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 が偶数か奇数かを判定せよ。 解法 一般に、整数 N が偶数かどうかを判定する方法は、if (N % 2 == 0) とすればよい。これを応用して解ける。 #include <bits/stdc++.h> using namespace std; i</bits/stdc++.h>…
「切り上げ処理」を要求する問題！ 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 の平均値を求め、小数点以下を切り上げて得られる整数値を答えよ。 解法 が偶数ならば、平均値は整数であって、答えは (a + b) / 2 となる が奇数ならば、平均値は…
これは易しめの A 問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 これらの数値の中から偶数のみを抽出せよ。 考えたこと for 文を回していって、偶数のみ出力すればよい。 #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vect</bits/stdc++.h>…
モノグサ社内で同僚と一緒に解いた！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。各 に対して次の問に答えよ。 先手と後手が交互にプレイする。整数 を管理する。最初 である。 先手は初手は を選び、 と に更新し、数列からその整数は削除す…
みたいな連立方程式を解いた経験があれば、思いつきやすいかもしれない。 問題へのリンク 問題概要 (インタラクティブ) 0 と 1 のみからなるサイズ の数列 があるが、未知である。いくつか質問を繰り返すことで、この数列を特定したい。 最大で 回まで質問す…
慣れないと頭がごっちゃになるけど、一度慣れればもう機械的に解ける系！！ 問題へのリンク 問題概要 のグリッドがある。各マスには '+' か '-' のいずれかの文字が書かれている。 最初、左上マスにコマが置かれている。高橋君と青木君は交互に、次の操作を…
グリッドを市松模様に塗って、「黒色マス」と「白色マス」で二部マッチングするという、超典型問題！ 問題へのリンク 問題概要 のグリッドが与えられます。 各マスは「障害物」が置かれているか、「空」であるかのいずれかです。入力データにおいては、障害…
ちょっと面白い問題！ 競プロ始めたばかりの方々に、計算量のことを意識させるのに良い問題かもしれない。 問題へのリンク 問題概要 どの 2 つの値も互いに相異なるような、長さ の数列 が与えられる。 この数列 の異なる 2 要素の和として表せる値の中に偶…
XOR は 2 回やると元に戻る！！！(素振り！) 問題へのリンク 問題概要 非負整数 が与えられます。 ^ = を満たす整数 を求めてください。 制約 XOR とは XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事…
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
面白かった！ 問題へのリンク 問題概要 個の石の山がある ( は偶数)。 番目の山には 個の石がある。先手と後手が交互に以下の操作を行う。操作できなくなった方が負けである 石の山のうち、まだ石が 1 個以上残っている山をちょうど 子選ぶ そのそれぞれの山…
「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。 問題へのリンク 問題概要 マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また…
一見すると かかるように思えるかもしれない。でも実は になる。 問題へのリンク 問題概要 個の整数 が与えられる (それぞれ 0 または 1)。このとき、 個の 0-1 変数 の値を、以下の条件を満たすように定めよ。 各 に対して、 を 2 で割ったあまりが に一致…
これを本番間に合わせられたなかったのは辛かった... あと、数え上げパートがあんなにスマートにはできなかった。無限に から落とせなかった... 問題へのリンク 問題概要 黒石さんと白石さんは、一列に並んだ 個のマスからなる盤面を使って遊んでいます。 マ…
最初与えられる文字列が高橋くんの手だと勘違いして、サンプル 2 が無限にわからないとなっていました。 clar でお騒がせいたしました...ありがとうございます。 問題へのリンク editorial 問題概要 高橋くんと青木くんがジャンケンを 回行う。青木くんの出…
