• 問題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
• 余談
  題名がオレンジなのに日本語問題文はみかんにするのね

いまさらこの言葉知った

これもメモっとく

raw 文字列を使ってエスケープ文字を省略する https://ez-net.jp/article/4C/WGk3uhdH/GozyeHzW2eq_/

• これはMathJaxてやつかな？ https://qiita.com/PlanetMeron/items/63ac58898541cbe81ada
• コードブロック内で数式使えない？

 math

    
\lim_{x \to \infty} f(x) \\
\lim_{h \to 0} \frac{f(x+h)-f(x)}{h} \\
\lim_{\substack{x \to \infty \ y \to \infty}} f(x,y)


  

• 色々使ってみた

$$x_{n+1} = rx_n(1-x_n)$$
\ $$\sum_{N=0}^{N}$$
\ $$えりか < つぼみ$$
\ $$ \begin{pmatrix} ♤ & ♡ ◇ & ♧ \end{pmatrix} $$

$$1 + 2 + 3 + 4 = ? $$ $$1 + 2 + 3 + 4 = \sum_{N = 1}^{4} = (5×4) / 2 = 10$$

$$ N = 1 + 2 + 3 + 4 2N = (1 + 2 + 3 + 4) × (4 + 3 + 2 + 1) = (1 + 4) + (2 + 3) + (3 + 2) + (4 + 1) = 5 × 4 N = 2N / 2 = (5 × 4) / 2 = 10 $$

• コードブロック使ってみた

 undefined

    
import re

MAHO = "キュアップ・ラパパ、怪物よ！あっちへいきなさい！"

reg = r"^キュアップ・ラパパ"

flag = re.search(reg, MAHO)

if flag:
    print("いま、キュアップ・ラパパていいました？")
else:
    print("べっ、別に失敗してないし！")

  

なるほどわからん！

基本的にナップサック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

ちなみに公式解説ではstackを使った方法を紹介しているが、3文字以上になった場合は煩雑になるのでC++で短い文字列を消すなら解答例の方が汎用的で良いかなと思ってます。

座標圧縮するだけとしか言いようがないw

座標圧縮はこのようなソートと二分探索をつかう方法と解答例のような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;と
解答用の配列vectorintans;
を用意しておいて

• 一番右は頂点無しなので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