茶色diff
差分更新を上手にやっていくという、とても教育的な問題！！！ そして、よく似た類題として、以下の問題がある！！ atcoder.jp 今回の問題へのリンク 問題概要 個の整数 が与えられる。以下の 回のクエリに答えよ。 各クエリでは 2 つの整数 が与えられる 数…
一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…
回操作した後の結果を求めよ (ただし がめちゃくちゃ大きい) という問題は、 同じ処理の繰り返しとなっているところを見抜く ダブリングする というパターンが多いと思われる。 問題へのリンク 問題概要 個の町 がある。町 からは、町 へテレポートできる。…
久しぶりに素因数分解する問題が来た！！！！！！！！！！！ 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…
誤差は怖い！！！！！！！ 問題へのリンク 問題概要 整数 と、"x.yz" のフォーマットで与えられる実数 が与えられる。 の小数点以下を切り捨て、結果を整数として出力せよ。 制約 考えたこと 数値誤差が怖いというテーマの問題は、パナソニックコンでもあっ…
気づけば一発系。ただし、数式の見た目がエグく見えてしまうかもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数 に対する - の値の最大値を求めよ。 制約 考えたこと 全探索すれば だけど、それでは間に合わない。さて、式の…
これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う！！ 問題へのリンク 問題概要 底面が一辺 cm の正方形であり、高さが cm であるような直方体型の水筒に、体積 cm3 の水を入れる。 底面の正方形の一辺を軸として、この水筒を…
ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…
落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…
丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…
差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…
先頭と末尾の両方から push できるデータ構造といえば、deque！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個の操作を行ってできる文字列を出力せよ type 1： 文字列 を左右反転する type 2： 値 F と文字 c が与えられ、F = 1 のと…
全探索した！ 整数を string 型にするのに手こずってしまった。 問題へのリンク 問題概要 以下の条件を満たす整数があれば、それを出力し、存在しなければ -1 を出力せよ。 ちょうど 桁である 左から数えて 桁目は である。() 制約 考えたこと 存在しない場…
期待値の線形性！！！ 問題へのリンク 問題概要 個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。 隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。…
結構ギャグ要素強めな問題だった 問題へのリンク 問題概要 3 つの整数 が与えられる。 長さ の整数列 であって、以下の条件を満たすものを構築せよ: を満たすような の組がちょうど 個ある 制約 考えたこと とりあえず一つ思うこととして、 は全部 1 以上な…
next_permutation の練習になりそう。DFS でも。 問題へのリンク 問題概要 の順列 が与えられます。 が の順列のうち辞書順で何番目か が の順列のうち辞書順で何番目か を求め、それらの差を答えよ。 制約 考えたこと 制約が小さいので、 通りの順列をすべ…
二分探索の教育的問題ですね！ 問題へのリンク 問題概要 正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき を満たす最大の正の整数 を求めよ。 制約 考えたこと わけわからない式だし、二分探索に決まってるやろ！！！という雰囲気があ…
教育的ないい問題！！！！！ 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか？ 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…
あるあるあるある。 問題へのリンク 問題概要 人がいてそれぞれの AtCoder レーティングが与えれている。1 以上 4800 以下で、400 ごとに色が変わるという設定。 今、レーティング 3200 以上の人は自由に色を変えることができる。このとき、 人の中に存在す…
高校数学で 「 を整数として は 3 の倍数であることを示せ」 という問題はよくあったと思う。これは「連続する 3 整数には 3 の倍数が含まれる」というのが理由になっている。今回こんな感じのことを考える。 問題へのリンク 問題概要 2 つの整数 があたえら…
確かに 200 点かもしれないけど、AGC-A は時々こういう注意力系が出るね。 問題へのリンク 問題概要 個の整数であって、最小が 、最大が であるようなものについて、その総和として考えられる値が何通りあるかを求めよ。 制約 考えたこと この手の問題で重要…
いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題ですね。 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべ…
「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では (B 以下の整数のうちの〜を満たすものの個数) から (A-1 以下の整数のうちの〜を満たすものの個数) を引く とすると、すごくやりやすい！！！！！ このテクニックは大昔の topcode…
長方形を直線で真っ二つに割る方法について 直線が長方形の対角線の交点を通る 直線が長方形を二等分する というのは同値だという話。結構、中学受験の算数では定番の話だったりする。 問題へのリンク 問題概要 二次元平面上で を頂点とした長方形と、その内…
いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …
確率を確実に 問題へのリンク 問題概要 正の整数 が与えられる。 最初に の整数値をランダムに出力する。以降コインを振って 表が出たら整数値を 2 倍する ( 以上になったら「勝ち」でゲーム終了) 裏が出たら整数値を 0 にする (こうなった時点で「負け」で…
こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。 問題へのリンク 問題概要 すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。 持っているビスケットを…
これと大体一緒かな。 むしろ合計枚数に関する制約がない分、やや難しくなっているかもしれない。 問題概要 を正の整数とする。 を満たすような 0 以上の整数 の組が何通りあるか求めよ。 制約 考えたこと 愚直に探索しようと思うと int res = 0; for (int r…
結構難しい... 問題へのリンク 問題概要 人全員が最初都市 1 にいて、全員を都市 1 -> 2 -> 3 -> 4 -> 5 -> 6 へと順番に進んで、全員が都市 6 にいる状態にしたい。 都市 1 から都市 2 への移動手段は毎秒ごとに提供されているが、同時に 人しか行けない。…
これも累積和！！！ ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com
