けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

テーマにストーリー性のある面白い問題

AtCoder ABC 185 A - ABC Preparation (灰色, 100 点)

面白い問題! 問題へのリンク 問題概要 コンテストを開くための 100, 200, 300, 400 点問題がそれぞれ 問ずつあつ。 100, 200, 300, 400 点問題を 1 問ずつ集めることで 1 回のコンテストを開くことができる。 何回のコンテストを開くことができるか。 解法 …

AtCoder ABC 183 A - ReLU (灰色, 100 点)

if 文を使ってもいいし、関数 max() を使ってもよい。 問題へのリンク 問題概要 整数 が与えられる。 ならば を出力せよ ならば 0 を出力せよ 解法 (1):if 文 if 文を用いて、 であるかどうかを判定して、処理を分けよう。 #include <bits/stdc++.h> using namespace std; </bits/stdc++.h>…

JOI 予選 2007 E - 品質検査 (AOJ 0514, 難易度 5)

この辺りから難しくなって来てる。「 で合格・不合格」という条件をどのように適切に言い換えるかが問われている。 問題へのリンク 問題概要 電源が 個、モーターが 個、ケーブルが 個ある。電源は と番号づけられていて、モーターは と番号づけられていて、…

AtCoder ABC 307 F - Virus 2 (黄色, 550 点)

セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…

AtCoder ABC 303 D - Shift vs. CapsLock (茶色, 400 点)

ランレングス圧縮をする問題に一瞬見えるかもしれない。でもそんなことしないで、最初から最後まで綺麗に DP で殴れる! 問題へのリンク 問題概要 文字 'a' と 'A' のみからなる長さ の文字列 が与えられる。 以下のキーボード操作を繰り返すことで、この文…

AOJ 2567 SIRO Challenge (JAG 模擬地区 2013 C) (400 点)

「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題! 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは …

AtCoder ABC 213 A - Bitwise Exclusive Or (100 点)

XOR は 2 回やると元に戻る!!!(素振り!) 問題へのリンク 問題概要 非負整数 が与えられます。 ^ = を満たす整数 を求めてください。 制約 XOR とは XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事…

JOI 春合宿 2011 day4-3 IOI (難易度 6)

lower_bound を上手に駆使する系 ジャッジページへのリンク 問題概要 人の選手が、コンテストに参加している。各選手の現在の得点は である。 どの選手についても、今後加算される可能性のある得点は、 点以上 点以下となっている ( 問中 問の競技が終了して…

AtCoder ABC 183 D - Water Heater (茶色, 400 点)

条件反射でいもす法!!! 問題へのリンク 問題概要 人がいる。 人目の人は、時刻 から時刻 の間で、毎分 リットルずつお湯を使う。 どの時刻においても、使用されているお湯の合計量が、毎分 リットル以内におさまるかどうかを判定せよ。 制約 考えたこと …

Codeforces Round #625 (Div. 1) B. Navigation System (R1800)

似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題! 問題へのリンク 問題概要 重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通…

AtCoder ABC 131 D - Megalomania (茶色, 400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題ですね。 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべ…

AtCoder AGC 012 A - AtCoder Group Contest (茶色, 300 点)

これほとんど drken1215.hatenablog.com と同じ問題!!! 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…

AtCoder ABC 078 C - HSI (ARC 085 C) (茶色, 300 点)

期待値に関するセンスがちょっと求められる問題 問題へのリンク 問題概要 高橋君はテストケースが ケースある Yes/No 判定問題に対して、ソースコードを提出したところ 問で TLE して、残りの 問は正解しました。 そこで「 問については 100ms で正解し、残…

AtCoder AGC 001 A - BBQ Easy (200 点)

伝説の始まり 問題へのリンク 問題概要 個の整数 が与えられる。 これらを 個ずつ 組作り、各組についての「小さい方の値」の総和を最大にしたい。 制約 考えたこと 小さすぎる値と大きすぎる値とを組合せてしまうと、大きい値が小さい値に吸収されてしまっ…

AOJ 2892 しりとり圧縮 (AUPC 2018 day3 D)

迷走しないようにしたい問題。 問題へのリンク 問題概要 banana at tomb but tos sound does some のようなしりとりが与えられる。同じ文字で始まるところは 1 つにつぶすことができる。上の例で言えば (banana at tomb but) (tos) (sound does some) という…

AOJ 2427 ほそながいところ (JAG 夏合宿 2012 day2-D) (800 点)

「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。

AtCoder ABC 314 A - 3.14 (灰色, 100 点)

円周率の問題が出るのは多くの人が想定していた。円周率を文字列にしてしまえばいいという発想が少し難しいかもしれない。また、添字計算が少し大変だったかもしれない。 問題へのリンク 問題概要 円周率 の小数点第 100 位までは 3.14159265358979323846264…