macle

joined 2 years ago
MODERATOR OF
 
  • 問題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

  • 余談
    題名がオレンジなのに日本語問題文はみかんにするのね

1
10→2進数変換 (lm.korako.me)
submitted 2 years ago* (last edited 2 years ago) by [email protected] to c/[email protected]
 
N = 17   #10001
ans = ""
while N > 0:
    ans = ans + str(N % 2)
    N //= 2
ans = ans[::-1]
print(ans) # 10001と出力

1
submitted 2 years ago* (last edited 2 years ago) by [email protected] to c/[email protected]
 

いまさらこの言葉知った

これもメモっとく

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

1
テスト (lm.korako.me)
submitted 2 years ago* (last edited 2 years ago) by [email protected] to c/[email protected]
 
\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 $$

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

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

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

flag = re.search(reg, MAHO)

if flag:
    print("いま、キュアップ・ラパパていいました?")
else:
    print("べっ、別に失敗してないし!")
1
トロプリ2期 (twitter.com)
submitted 2 years ago* (last edited 2 years ago) by [email protected] to c/[email protected]
 

 

なるほどわからん!

 

基本的にナップサックDPだが宝箱の状態をbitで管理する
dp[i][j] iは鍵番号、jはbitが立ってる番号が宝箱開封済とする

解答例(C++) https://atcoder.jp/contests/abc142/submissions/27600466

1
submitted 2 years ago* (last edited 2 years ago) by [email protected] to c/[email protected]
 

文字列が短いので左端と右端をすべて探索しても間に合う(解答例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

1
submitted 2 years ago* (last edited 2 years ago) by [email protected] to c/[email protected]
 

特定の連続する文字列を消す問題

今回のように短い文字列を消す場合は典型的な方法がある。

空の文字列の後ろに入力した文字列を左から追加していく。追加毎に後ろの文字が消す文字になっているか確認する。(今回の場合は後ろ二文字を確認すれば良い。)消す文字だった場合は消す文字の数を後ろから消せば良い。  

解答例(C++)
https://atcoder.jp/contests/agc005/submissions/27596768

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

 

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

座標圧縮はこのようなソートと二分探索をつかう方法と解答例のようなstd::setとstd::mapを使う方法がある。(他にもあるのかな?)

解答例(C++)
https://atcoder.jp/contests/abc213/submissions/27596747

view more: next ›