- 問題URL https://atcoder.jp/contests/abc195/tasks/abc195_b - 問題メモ A(最小の重さ) B(最大の重さ) W(合計の重さ) - 重さがキログラム単位だと扱いにくいのでグラム単位に変換（1000を掛ける） - みかんの数を全部探索する。 重さにあったオレンジの数が用意できる条件は A * (みかんの数) <= W <= B *　(みかんの数) である。よってこの条件のときの数の時に最大数と最小数を更新すれば良い。 一回も更新されてなかったらどの数でも用意できなかったということになるのでUNSATISFIABLEを出力 - ソース https://github.com/mofrun/Competitive-programming/blob/main/AtCoder/ABC195/B%20-%20Many%20Oranges.cpp - 余談 題名がオレンジなのに日本語問題文はみかんにするのね

``` N = 17 #10001 ans = "" while N > 0: ans = ans + str(N % 2) N //= 2 ans = ans[::-1] print(ans) # 10001と出力 ```

いまさらこの言葉知った これもメモっとく raw 文字列を使ってエスケープ文字を省略する https://ez-net.jp/article/4C/WGk3uhdH/GozyeHzW2eq_/

なるほどわからん！

基本的にナップサックDPだが宝箱の状態をbitで管理する dp[i][j] iは鍵番号、jはbitが立ってる番号が宝箱開封済とする 解答例（C++） https://atcoder.jp/contests/abc142/submissions/27600466

文字列が短いので左端と右端をすべて探索しても間に合う（解答例1) 左から数えて一番大きいACGT文字列を出力するほうが計算量少ない（解答例2） 解答例1だと1000文字以上から間に合うか怪しそう。今回は関係ないが。 計算量は文字列をNとして、解答例1がO(N^2)で解答例2がO(N) 解答例1(C++) https://atcoder.jp/contests/abc122/submissions/27599924 解答例2(C++) https://atcoder.jp/contests/abc122/submissions/27599955

X - A <= 0の場合は売り切れ、売り切れでない場合は最小価格になるか判定すればよい。 答えの変数が初期値のままの場合はどの店でも買えなかったということなので-1を出力。初期値以外の場合はそのまま答えの変数を出力すれば良い。

愚直にやると縦の座標×横の座標×A×Bで計算量は300×300×300×300>10^9にはなりそうなので間に合わない。 座標の全探索はどうにもならなそうなのでA×Bを改善したい。 実はAだけ加えたものが良い盤面であればBはいくつでも良い盤面である。 よってA方面だけ探索して良い盤面一つにつきN個良い盤面として答えの変数に加えれば良い 解答例(C++) https://atcoder.jp/contests/agc023/submissions/27597329

特定の連続する文字列を消す問題 今回のように短い文字列を消す場合は典型的な方法がある。 空の文字列の後ろに入力した文字列を左から追加していく。追加毎に後ろの文字が消す文字になっているか確認する。(今回の場合は後ろ二文字を確認すれば良い。)消す文字だった場合は消す文字の数を後ろから消せば良い。　　 解答例(C++) https://atcoder.jp/contests/agc005/submissions/27596768 ちなみに[公式解説](https://img.atcoder.jp/data/agc/005/editorial.pdf)ではstackを使った方法を紹介しているが、3文字以上になった場合は煩雑になるのでC++で短い文字列を消すなら解答例の方が汎用的で良いかなと思ってます。

座標圧縮するだけとしか言いようがないw 座標圧縮は[このような](https://algo-logic.info/coordinate-compress/)ソートと二分探索をつかう方法と解答例のようなstd::setとstd::mapを使う方法がある。(他にもあるのかな？) 解答例(C++) https://atcoder.jp/contests/abc213/submissions/27596747

「5が2つだけあること」「7が1つだけあること」の両方の条件がそろっていたらYESである。 条件の判定は色々あるが、数列でカウントして判定した。（下記リンク参照） 解答例（C++） https://atcoder.jp/contests/abc042/submissions/27596651

コンテスト毎に必ずすべての問題を一つずつ使うので、一番少ない問題の数しかコンテストを開けない。 よって一番少ないAを出力すれば良い。 解答例（C++）　　 https://atcoder.jp/contests/abc185/submissions/27596643

#のY座標とX座標をそれぞれ座標圧縮する その際に解答の高さと幅もわかるので解答用のリストを作る #の座標を圧縮した座標に#を解答用リストに入力後に出力すればよい 解答例(C++) https://atcoder.jp/contests/abc107/submissions/27575249

学校の数学のように解くことも可能だが、これは競技プログラミングなのでコンピューターの計算力を頼ってみる。 該当する数字をXとする。Xの数字を総当りしたい。どこまで総当りすればいいかが知りたい。 Aだけで考えるとA <= 100なのでX<= 1000まで総当りすればよさそう。Bだともう少し増えそうだが1100よりは小さそう。 正直10000にしても計算は間に合うので適当に100000まで総当りする。 判定については切り捨てや誤差が気になるのでx * 8 / 100のように先に掛け算して数字をふくらませると防止できる。 解答例（C++） https://atcoder.jp/contests/abc158/submissions/27573156

+ 変数を宣言 + 変数に入力 + かけた数値を出力 正直やるだけ問題。競プロ初心者にはよいかもしれない。 なれない言語の出力、入力の練習にも使えそう。 解答例(C++) https://atcoder.jp/contests/abc169/submissions/27570280 解答例 (Python) https://atcoder.jp/contests/abc169/submissions/27571148 解答例(Ruby) https://atcoder.jp/contests/abc169/submissions/27571405

サンプル1(出力例1の下にある)図を右からやっていく形 連結成分を数えるint cnt = 0;と 解答用の配列vector\<int\>ans; を用意しておいて + 一番右は頂点無しなのでansに0を挿入 + 次は頂点6が一個加わるのでcntに1を足しansにcntを挿入 + 頂点5以降だが、まず頂点が一つふえるのでとりあえずcntに1つ足す。現在の頂点より大きい頂点と今まで連結しておらず新規に連結するようだったら連結成分が減るのでcntから1引く。 その後ansにcntを挿入する 連結してるかどうかの判定はUnionFindを使えばよい。 ansは順番が逆になっているので、C++であればreverseで順番を戻して出力 解答例（C++) https://atcoder.jp/contests/abc229/submissions/27568298

愚直にやるなら左端と右端を決めて探索していけばよいが… 文字列の長さをN（最大2 * 10^5）として愚直に探索する擬似コードを書くと for left = 0 ; left < N; left++ 　　　　for right = 0; right < N; right++ となるがこれは計算量が最大でN * N(4 * 10^10)となり実行時間制限: 2 sec内で探索はできない。(大抵は10^8以下でないと間に合わない) よって工夫する必要がある。rightのループ文を高速化できればN *(高速化したやつ)にできるぽい やり方としてパっと浮かぶのは累積和としゃくとり法を使う方法。もう一つは Twitterで教えてもらった累積和と二分探索法。 これらの説明は難しいのでソースで。 解答例（C++、愚直に探索、計算量が多すぎてTLE(制限時間オーバーによる誤答)になってます ） https://atcoder.jp/contests/abc229/submissions/27567341 解答例（C++、累積和、しゃくとり法） https://atcoder.jp/contests/abc229/submissions/27565090 解答例（C++、累積和、二分探索） https://atcoder.jp/contests/abc229/submissions/27565460

美味しさが大きいほうから選んでいけば良い 実装的にはvector<pair<long long, long long>>に入力して大きい順にソートすれば良い。 あとは数え上げるだけ。（解答例みてください） 解答例（C++） https://atcoder.jp/contests/abc229/submissions/27564478

1の桁から足し合わせて調べていく 手順としては 1. 一番下の桁は10で割ったあまりなのでA%10 + B%10を求める 2. 1で求めた数字が10以上であれば繰り上がりがあるのでHard出力 3. 上の桁を求めたいので1番下の桁を消す。10で割れば消すことができる これをすべての桁を調べるまで繰り返す 解答例 https://atcoder.jp/contests/abc229/submissions/27564088

#. .# か .# #. 以外はYesなのでif文で判定すれば良い 解答例（C++） https://atcoder.jp/contests/abc229/submissions/27564011