atcoder.jp 問題 $H \times W$のマス目と、$N$枚のタイルが与えられるよ $i$枚目のタイルは、$ A_i \times B_i $の長方形だよ タイルを使って、マス目をピッタリ埋める事ができる？ 重なったり、空白があったりしちゃだめだよ タイルは回転させてもいいよ 成…

atcoder.jp 問題 文字列$S$が与えられるよ 次の操作を1回行った後の文字列として、有り得るものはいくつある？ Sのうち2つの文字を選んで、入れ替える 成約 $2 \leq |S| \leq 10^{6}$ 思考 $O(N^{2})$は通らない… 片方を全探索して、もう片方がサクサクッと…

atcoder.jp 問題 整数$X$が与えられるよ $ \lceil \frac{x}{10} \rceil $を出力してね 成約 $-10^{18} \leq X \leq 10^{18}$ 思考 math.ceilで行けるでしょｗｗｗ 誤差で通らず無事致命傷 ちゃんと切り上げ除算、関数で準備しておきませう、というTips コー…

atcoder.jp 問題 "<"、"="、">"で作られた文字列$S$が与えられるよ $S$が、双方向矢印型かどうか判定してね 成約 $3 \leq |S| \leq 100$ 思考 最初が"<"、最後が">"、それ以外が"="かどうかを判定すれば良いね コード S = input() if S[0] == "<" and S[-1] …

atcoder.jp 問題 長さ$N$の数列$A$が与えられるよ Q個のクエリを順番に処理してね クエリ1：$A$の中の要素$x$の直後に$y$を挿入してね クエリ2：$A$の中にある要素$x$を削除してね 全部のクエリを捌いた後の$A$はどうなってる？ 成約 $1 \leq N \leq 2 \time…

atcoder.jp 問題 最初に文字列$T$と、空文字列$S$を持ってるよ 文字列がいくつか入った袋が$N$個あるよ 袋$i$には、$A_i$個の文字列が入ってるよ 以下の手順を$i=1,2,...,N$について繰り返すよ 1円を払って、袋$i$から好きな文字列を1つ選んで、文字列$S$の…

atcoder.jp 問題 3個の数列$A,B,C$が与えられるよ 長さ$Q$の数列$X$も与えられるよ 各$i=1,...,Q$について、以下の問題に答えてね $A,B,C$から要素を1つずつ選んで、和を$X_{i}$にすることができる？ 成約 $1 \leq |A|,|B|,|C| \leq 100$ $0 \leq A_i, B_i ,…

atcoder.jp 問題 $N$個の整数$A$が、1行に1つずつ与えられるよ $N$は入力では与えられないよ $A_{N}=0$だよ！ Aを逆順に出力してね！ 成約 $1 \leq N \leq 100$ $1 \leq A_{i} \leq 10^{9} (1 \leq i \leq N-1)$ $A_{N} = 0$ 思考 最後の入力(=0)までずっと…

atcoder.jp 問題 文字列$S$が与えられます 英小文字と、ちょうど2つの"|"が含まれるよ 2つの"|"と、その間にある文字を削除した文字列を教えてね 成約 $2 \leq |S|\leq 100$ 思考1 文字列を、"|"で分割して、先頭のパーツと末尾のパーツだけ取り出せたら良い…

atcoder.jp 問題 長さNの数列Aが与えられるよ Q個のクエリを捌いてね タイプ1：$A_{i}$をxに変更 タイプ2：区間$l,r$の中で、2番目に大きい値の個数を出力 成約 $1 \leq N,Q \leq 2 \times 10^{5}$ 思考 こねこねしてダメ元でSQLite投げてみたりしたけどダメ…

atcoder.jp 問題 1辺7の立方体を、座標空間上に3つ配置するよ V1,V2,V3が与えられるよ 3つの立方体のうち、丁度1つに含まれる領域の体積がV1 3つの立方体のうち、丁度2つに含まれる領域の体積がV2 3つの立方体のうち、丁度3つに含まれる領域の体積がV3 にな…

atcoder.jp 問題 N人の選手がコンテストに参加するよ。みんな最初は0点だよ 今から$i$秒後に、選手$A_i$が、$B_i$点増加するよ $i+0.5$秒後に、選手たちの得点は何種類？ 成約 $1 \leq N,T \leq 2 \times 10^{5}$ $1 \leq B_i \leq 10^{9}$ 思考 大人しくシ…

atcoder.jp 問題 正整数Nが与えられるよ 正整数以下の回文立方数のうち、最大値を教えてね 成約 $1 \leq N \leq 2 \times 10^{18}$ 思考 N以下の回文ではない立方数を考えてみる $10^{6}^{3} = 10^{18}$なので、$10^{6}$まで、順に3乗の値を見ていけば良さそ…

atcoder.jp 問題 N個の駅があるよ！ 電車の情報がM個与えられるよ！ 駅Aから駅Bまで、cの時間がかかるよ！ l,l+d,l+2d,...,l+(k-1)dの時刻に駅Aから列車が発車するよ！ 以下の一覧を求めてね！ 駅1から駅Nに到着できる最終時刻 駅2から駅Nに到着できる最終時…

atcoder.jp 問題 長さNの非負整数列Aが与えられるよ 以下の条件を満たす整数組$(i,j)$は何個ある？ $1 \leq i < j \leq N$ $A_i \times A_j$は平方数 成約 $2 \leq N \leq 2 \times 10^{5}$ $0 \leq A_{i} \leq 2 \times 10^{5}$ 思考 iとjを全部見ていくの…

atcoder.jp 問題 長さNの文字列Sが与えられるよ 以下の操作をQ回繰り返すよ 文字$c_i$を$d_i$で置き換える 全部終わったら文字列はどうなる？ 成約 $1 \leq N,Q \leq 2 \times 10^{5}$ 思考 基本的に、クエリを全部舐めて「この文字はこれになって…」を整理…

atcoder.jp 問題 0と1で作られた文字列があるよ 0と1が交互に出てくる文字列を良い文字列と呼ぶよ 以下のクエリを処理してね！ 1：L文字目からR文字目までの0と1を反転させてね！ 2：L文字目からR文字目までをそのまま抜き出した時、その文字列は良い文字列…

atcoder.jp 問題 整数N,M,Kが与えられるよ NとMは異なるよ NとMのうち、どちらか一方のみで割り切れる数のうち、小さい方からK番目のものを教えてね！ 両方で割り切れる数は除くよ！ 成約 $1 \leq N,M \leq 2\times 10^{8}$ $1 \leq K \leq 10^{10}$ 思考 と…

atcoder.jp 問題 高橋くんがH行W列のグリッド上のどこかのマスに不時着したよ 高橋くんは、LRUDの文字列に沿って移動したよ 高橋くんは移動中に海を通ってないよ 高橋くんが不時着した可能性のあるマスの個数を数えてね 成約 $3 \leq H,W \leq 500$ $1 \leq …

atcoder.jp 問題 円状に並んだN個の箱があるよ 箱iには、$A_{i}$個のボールが入ってるよ 1~Mまで、以下の操作を行うよ 変数Cを0とする 箱$B_i$の中のぼーるを全部出して、箱$B_i+1$から順に1つずつ入れていくよ すべての操作を終えた時に、各箱に入っている…

atcoder.jp 問題 TVゲームをしてるよ 今は始めたばかりなので、ステージ1しか遊べないよ ステージ$i$を$A_{i}$秒かけてクリアすると、ステージ$i+1$が遊べるよ ステージ$i$を$B_{i}$秒かけてクリアすると、ステージ$X_i$が遊べるよ ステージ$N$が遊べるよう…

atcoder.jp 問題 整数Nが1つだけ黒板に書かれてるよ 2以上の整数が全てなくなるまで、以下の操作を繰り返すよ 2以上の整数を1つ選んで、$x$とする $x$を1つ消して、$\lfloor \frac{x}{2} \rfloor$と、$\lceil \frac{x}{2} \rceil$を この操作で、お金が$x$円…

atcoder.jp 問題 H行W列のグリッドが与えられるよ グリッドが赤、緑の2色で塗り分けられてるよ 赤色のマスをランダムで1つ選んで、緑色に塗り替えるよ 塗替えた後の、緑色の連結成分数の期待値をmod998244353でお願い！ 成約 $ 1 \leq H,W \leq 1000$ 赤色の…

atcoder.jp 問題 ソリがN台あるよ それぞれのソリを引くために必要なトナカイが、ソリ毎によって違ったりするよ 以下のクエリに答えてね トナカイがX匹居たら、最大何台のソリ引ける？ 成約 $ 1 \leq N,Q \leq 2 \times 10^{5}$ $ 1 \leq R_{i} \leq 10^{9}$…

atcoder.jp 問題 N組の靴下があったよ i番目の組の靴下は、色iだよ K枚の靴下がなくなってたよ 靴下のペアの奇妙さは、左右の色の差の絶対値だよ 残ってる靴下の組み合わせで、最小の奇妙さはいくつ？ 残ってる靴下の枚数が奇数なら、1枚使わない靴下ができ…

atcoder.jp 問題 長さNの数列が与えられるよ Aの部分列で、かつ、隣接する2項の差の絶対値がD以下であるものを作って欲しい 条件を満たす部分列のうち、一番長いものの長さを教えて！ 成約 $1 \leq N \leq 5 \times10^{5}$ $0 \leq D \leq 5 \times10^{5}$ $…

atcoder.jp 問題 $N\times N$のグリッド板があるよ 各マスは、空きマス、障害物のどちらかだよ プレイヤーのコマが盤上に2つ存在するよ 板を上に傾けると、プレイヤーのコマが同時に1マス上に移動しようとするよ 移動先が障害物なら、そのプレイヤーは動けな…

atcoder.jp 問題 バスが走ってるよ N個のバス停で、バスの中の人が$A_i$変化したよ バスの中の人は、最終的に何人？考えうる最小値を答えてね 成約 $1 \leq N \leq 2 \times 10^{5}$ $-10^{9} \leq A_i \leq 10^{9}$ 思考 最初0人からスタートすると、途中の…

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…