テーマにストーリー性のある面白い問題
基本情報科目 B でもよく出題されるテーマですね! 問題へのリンク 問題概要 整数値 () が与えられる。 ならば、4 ならば、6 ならば、8 を出力せよ。 解法 if 文のほどよい練習問題!! #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; if (N </bits/stdc++.h>…
面白い問題! 問題へのリンク 問題概要 コンテストを開くための 100, 200, 300, 400 点問題がそれぞれ 問ずつあつ。 100, 200, 300, 400 点問題を 1 問ずつ集めることで 1 回のコンテストを開くことができる。 何回のコンテストを開くことができるか。 解法 …
if 文を使ってもいいし、関数 max() を使ってもよい。 問題へのリンク 問題概要 整数 が与えられる。 ならば を出力せよ ならば 0 を出力せよ 解法 (1):if 文 if 文を用いて、 であるかどうかを判定して、処理を分けよう。 #include <bits/stdc++.h> using namespace std; </bits/stdc++.h>…
if 文を用いてもいいが、もっと楽にできる! 問題へのリンク 問題概要 0 か 1 である整数 が与えられる。 ならば 1 を出力し、 ならば 0 を出力せよ。 解法 if 文を用いてもよいが、 を出力するのが簡単だ。 #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…
この辺りから難しくなって来てる。「 で合格・不合格」という条件をどのように適切に言い換えるかが問われている。 問題へのリンク 問題概要 電源が 個、モーターが 個、ケーブルが 個ある。電源は と番号づけられていて、モーターは と番号づけられていて、…
セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…
ランレングス圧縮をする問題に一瞬見えるかもしれない。でもそんなことしないで、最初から最後まで綺麗に DP で殴れる! 問題へのリンク 問題概要 文字 'a' と 'A' のみからなる長さ の文字列 が与えられる。 以下のキーボード操作を繰り返すことで、この文…
「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題! 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは …
XOR は 2 回やると元に戻る!!!(素振り!) 問題へのリンク 問題概要 非負整数 が与えられます。 ^ = を満たす整数 を求めてください。 制約 XOR とは XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事…
lower_bound を上手に駆使する系 ジャッジページへのリンク 問題概要 人の選手が、コンテストに参加している。各選手の現在の得点は である。 どの選手についても、今後加算される可能性のある得点は、 点以上 点以下となっている ( 問中 問の競技が終了して…
条件反射でいもす法!!! 問題へのリンク 問題概要 人がいる。 人目の人は、時刻 から時刻 の間で、毎分 リットルずつお湯を使う。 どの時刻においても、使用されているお湯の合計量が、毎分 リットル以内におさまるかどうかを判定せよ。 制約 考えたこと …
似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題! 問題へのリンク 問題概要 重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通…
いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題ですね。 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべ…
これほとんど drken1215.hatenablog.com と同じ問題!!! 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…
期待値に関するセンスがちょっと求められる問題 問題へのリンク 問題概要 高橋君はテストケースが ケースある Yes/No 判定問題に対して、ソースコードを提出したところ 問で TLE して、残りの 問は正解しました。 そこで「 問については 100ms で正解し、残…
伝説の始まり 問題へのリンク 問題概要 個の整数 が与えられる。 これらを 個ずつ 組作り、各組についての「小さい方の値」の総和を最大にしたい。 制約 考えたこと 小さすぎる値と大きすぎる値とを組合せてしまうと、大きい値が小さい値に吸収されてしまっ…
迷走しないようにしたい問題。 問題へのリンク 問題概要 banana at tomb but tos sound does some のようなしりとりが与えられる。同じ文字で始まるところは 1 つにつぶすことができる。上の例で言えば (banana at tomb but) (tos) (sound does some) という…
「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。
円周率の問題が出るのは多くの人が想定していた。円周率を文字列にしてしまえばいいという発想が少し難しいかもしれない。また、添字計算が少し大変だったかもしれない。 問題へのリンク 問題概要 円周率 の小数点第 100 位までは 3.14159265358979323846264…