Greedy の本当に初歩の問題といえる。 問題へのリンク 問題概要 整数 1 がある。この整数に対して、以下のいずれかの操作を 回行う。 操作 A：整数値を 2 倍する 操作 B：整数値に を足す 操作後の整数値の最小値を求めよ。 制約 考えたこと 基本的に、「も…

面白かった！！ 問題へのリンク 問題概要 人がいて、それぞれ正直者であるか、嘘つきであるかのいずれかである。また、各人は混乱していないか、混乱しているかのいずれかである。 混乱していない正直者は、常に正しいことをいう 混乱している正直者は、常に…

日頃から「まずは全探索！」という意識があれば、この手の問題は全探索でできると気づけるはず！ 問題へのリンク 問題概要 ビーカーに対して、次の 4 種類の操作を好きな順序で好きな回数だけ実行する。 ビーカーに g の水を入れる ビーカーに g の水を入れ…

色々な解法があるが、set を使うのが楽。set のよい練習問題とも言える。 問題へのリンク 問題概要 最初何も書いていない黒板がある。次の 回の操作を行った。 回目の操作では、整数 を考える 黒板に が書かれていない場合は、新たに を黒板に書く 黒板に が…

for 文または while 文の練習問題 問題へのリンク 問題概要 正の整数 が与えられる。ある正の整数 が存在して を満たすことが保証される。 を求めよ。 制約 考えたこと と計算を続けていって、 に一致したところで break して、そのときの値を答えればよい。…

基本的な文字列操作の問題！ 問題へのリンク 問題概要 文字列 が与えられる。 の先頭の文字に "UPC" を付け加えてできる文字列を出力せよ。 考えたこと 文字列 S の先頭の文字は S[0] によって取得できる。その文字を出力したあと、続けて "UPC" を出力すれ…

完全既出は珍しい！ 問題へのリンク 問題概要 "6x4" のような、「一桁かける一桁」の計算を表す 3 文字の文字列 が与えられる。この計算結果を求めよ。 考えたこと この問題と完全に同じですね。 drken1215.hatenablog.com コード #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

「二項係数の和」は結構なんとかなることを学んだ！ 備忘録程度に書く。 問題へのリンク 問題概要 下の図のように、 グリッドを、レベル の L 字で隙間なく埋め尽くす (レベル の L 字の定義は問題文参照)。 マス を指定したとき、次の 回のクエリに答えよ。…

ICPC 本番に正解チームの現れなかった難問！ 問題へのリンク 問題概要 サイズのグリッドグラフから、いくつかの頂点と辺を削除してできる連結なグラフが与えられる。 このグラフの全域木であって、どの 2 つの葉も、その間の距離が偶数であるものを 1 つ求め…

久しぶりに簡単な問題の到来！ 問題へのリンク 問題概要 正の整数 が与えられるので、 の二乗の値を出力せよ。 考えたこと の二乗は、 (A + B) * (A + B) によって計算できる。これを実装すればよい。 コード #include <bits/stdc++.h> using namespace std; int main() { i</bits/stdc++.h>…

いろんな解法が考えられる。 問題へのリンク 問題概要 4 枚のカードがあって、それぞれのカードには整数 が書かれている。 ここに 1 枚カードを加え、フルハウスとできるか判定せよ。 制約 考えたこと 色んな解法が考えられるが、この手のものは「ソート」が…

実装が少し大変だった。そして、両端から Greedy で追い詰めていけばよいのは思いつかなかった。チームメイトが思いついていた。 問題へのリンク 問題概要 1 から までの整数が書かれたカードが合計で 枚あり、整数 の書かれたカードは 枚ある。各 に対して…

チーム戦で、hotman-san、アトリウムさんと一緒に解いて、協力ゲーという感じがして楽しかった！！ N の過程。協力ゲー感あってすごい楽しかった！！！hotman さん：「巡回する感じで結構行けるね」僕：「巡回でやってみたら、N が奇数の場合は、スコア 1 で…

極端な場合を考えて考察した！ 問題へのリンク 問題概要 非負整数 (片方は正) が与えられるので、以下の条件を満たすような二次元グリッドを構築せよ（存在しない場合は、そのことを報告せよ）。 グリッドのマス数は 以上 以下 グリッドの各マスは白色または…

全探索に慣れよう！ 問題へのリンク 問題概要 同じ文字列を二個連結してできるような文字列を「偶文字列」とよぶ。 与えられた偶文字列 について、末尾の文字を 1 文字以上消して作れる偶文字列のうち、その最大長を答えよ。 制約 考えたこと 全探索しよう！…

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

長さが大きい順に処理していこう！ 問題へのリンク 問題概要 長さが の棒がある。 これらの棒を 4 個選んで長方形を作りたい。作れる長方形の面積の最大値を求めよ。長方形を作れない場合は 0 と答えよ。 制約 考えたこと できるだけ大きい長さの棒を使いた…

最小公倍数を求めよう！ 問題へのリンク 問題概要 台の時計があり、時計 の針はちょうど 秒で時計盤を 1 周する。 最初、全ての時計の針は真っ直ぐ上に向いており、止まっている。イルカは、全ての時計の針を同時に動かし始めた。再び、全ての時計の針が真っ…

これは典型らしいので、このセグメント木の使い方は今後押さえる！ 問題へのリンク 問題概要 正の整数からなる数列 が与えられる。 一般に、数列 に対して、 とする。まず の値を求めて、その後、次の 回のクエリに答えよ。 【クエリ】 整数 が与えられるの…

で解けた！ 同じ値が連続する場合の対処に苦慮した。 問題へのリンク 問題概要 強さが のスライムが一列にこの順に並んでいる。 に対して、次の問に答えよ。 【問】 初期状態で左から 番目にいるスライムが高橋君である。高橋君が下記の行動を好きな回数だけ…

二重頂点連結成分分解して得られる Block-Cut 木のクエリに答えていく問題。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。次の 回のクエリに答えよ。 【クエリ】 各クエリでは 2 頂点 が与えられる。 個の頂点のうち、次の…

これ系の問題、最近あまり見かけなくなった気がする。 問題へのリンク 問題概要 個の正の整数からなる数列 が与えられる。 この数列の項を適切に並び替えることによって、「どの隣接する 2 項の積も 4 の倍数」となるようにできるかどうかを判定せよ。 制約 …

この手のものは関数化するのがオススメ！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のうち、2 で割れる回数が最大のものを求めよ（タイがないことが証明できる）。 制約 考えたこと 全探索しよう！ 具体的には、 について、「 を 2 …

とても面白かった。場合分けを詰め切るが大変だった。 問題へのリンク 問題概要 橋がただ 1 つだけ存在するような連結で単純な無向グラフをハシポンとよぶ。 頂点数 、辺数 の連結で単純な無向グラフが与えられる。このグラフに辺を追加することで、ハシポン…

Block-Cut 木を試すのにすごくいい問題！ 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる（単純とは限らない）。頂点 には、重み がついている。各頂点について、以下の問に答えよ。 【問】 その頂点を除外したグラフを考える。この…

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

現代の AtCoder にはあまりない「一行読み込み」を要求する問題 問題へのリンク 問題概要 "Left Left Right Right AtCoder" のように、"Left", "Right", "AtCoder" のいずれかを空白区切りで連結した文字列が一行で与えられる。 "Left" は "<" に replace し…

すごく面白い問題だった！ 二重頂点連結成分分解からの Block-Cut 木ライブラリを試す目的で解いてみた。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点について、次の問に答えよ。 その点を除去した上で、各点に対応する頂点数 のグラフを考…

計算量の意識が必要になる良問！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。これを左右に 2 つに分ける（左右ともに 1 個以上はとる）。 左側の要素の総和を 、右側の要素の総和を とするとき、 の最小値を求めよ。 制約 考えたこと もし…

ソートの練習！ 問題へのリンク 問題概要 個の整数 から 選んで総和をとる。 総和を取った値の最大値を求めよ。 制約 考えたこと 個の整数 を大きい順に並べておいて、大きい順に 個とって足せばよい。 C++ では、大きい順にソートするのは sort(l.begin(), …