atcoder.jp 問題 時計回りに1から2Nまで並んだ2N個の頂点があるよ $A_i$と$B_i$が弦で繋がってるよ 弦は交差してる？ 成約 $2\leq N\leq 2\times 10^5$ $A_i,B_j$はすべて相違なる 思考 セグ木がうまく扱えたら、どうにかなった…かなぁ 成約より、各頂点に結…

atcoder.jp 問題 N個の島があるよ i番目の島と、i+1番目の島が繋がってるよ N番目の島は1番目の島と橋で繋がってるよ 島M個を回るツアーがあるよ 橋の内どれか1本を壊したいんだけど、ツアーの長さの最小値はいくつになる？ 成約 $ 3 \leq N \leq 2 \times 1…

atcoder.jp 問題 N種類の食材があります 材料$i$は、$Q_i$あります 料理Aと料理Bがあります 料理Aを作るのに、材料$i$が$A_i$必要です 料理Bを作るのに、材料$i$が$B_i$必要です 料理Aと料理Bをあわせて何人前作れる？ 成約 $ 1 \leq N \leq 10$ $1 \leq Q_i…

atcoder.jp 問題 連結なN頂点の無向グラフが与えられるよ 頂点には数字が書かれてるよ 1からNまでの単純パス(同じ頂点を複数回通らない)のうち、一番スコアの高いパスのスコアを教えてね パスの頂点に書かれた数字が広義単調増加になってる場合、数字の種類…

atcoder.jp 問題 $N \times N$のグリッド上に、$N2-1$までの長さの紐と、高橋くんを設置してね 高橋くんは真ん中に設置してね 成約 $ 3 \leq N \leq 45 $ $ N $は奇数 思考 構築問題だ 高橋くん真ん中なので、ぐるぐる～っと螺旋書いたら良さそう 本番中はル…

atcoder.jp 問題 座標平面上で蛇のおもちゃを動かすから、どのパーツがどこにあるか教えてね 成約 $ 2 \leq N \leq 10^6 $ $ 1 \leq Q \leq 2 \times 10^5 $ 思考 クエリ毎に、愚直にシミュレーション dequeは添字アクセス遅いから、配列で誤魔化そうね 配列…

的中率 := 予想が当たる確率 回収率 := 投入した金額のうち何割返ってくる？ 20240127 * 文字コードぶっ飛んでたので、再度スクレイピング中

atcoder.jp 問題 インタラクティブだよ N本のジュースがあります。1本腐ってます 腐ってるものを飲むとお腹壊すよ 何人かの友人を呼んで、友人たちにジュースを振る舞ってね お腹を壊したかどうか教えてくれるから、腐ってるジュースを特定しましょう 特定す…

atcoder.jp 問題 グリッドが与えられるよ それぞれのマスには、o,x,.のどれかが書いてあるよ 好きな数だけ、.をoに変えることができるよ(操作) 縦横（斜め無し）でoが$K$個続くような盤面作りたいよ そんな盤面作れる？作れるなら、最小操作数教えてね 成約 …

atcoder.jp 問題 N人が居ます 人$i$は、人$A_i$のすぐ後ろに並んでます 列に並んでる人の番号を順番に出力してね 成約 $ 1 \leq N \leq 3 \times 10^{5}$ 思考 先頭か末尾が分かれば辿れるねぇ 先頭は、$A_i$が-1の人$i$… * じゃあ、先頭の人$i$が分かったら…

atcoder.jp 問題 N以下の正整数のうち、各桁の総和で割り切れるものはいくつありますか？ 成約 $ 1 \leq N \leq 10^{14}$ 思考 成約がぶっ飛びすぎ 桁DPを使う、らしい 暫くは「N以下で、◯◯の個数！」みたいなパターンでマッチして良さそう 上の桁から、「そ…

atcoder.jp 問題 数列Aが与えられるので、Aの中に入り込むピラミッド数列の最大の大きさは？ ピラミッド数列とは？ 1,2,...k-1,k,k-1,...,2,1みたいなやつ（長さ2k-1) 成約 $ 1 \leq N \leq 2 \times 10^{5}$ $ 1 \leq A_i \leq 10^{9}$ 思考 成約から、長さ…

atcoder.jp 問題 整数Nが与えられます 0,2,4,6,8だけが登場する整数が良い整数です 小さい方からN番目の整数を求めてね 成約 $ 1 \leq N \leq 10^{12}$ 思考 成約が大きい。やだ。 愚直に小さい方から1個ずつ求めていくわけではない気配 とりあえずサンプル…