記事一覧
[MC Digital プログラミングコンテスト2024] AHC031
暫定57位->システス58位でした。 https://atcoder.jp/contests/ahc031/submissions?f.User=merhorn ペナルティが2種類あって 1. 予約面積に足りない場合はarea_cost * 100…
Hello world
ft_printf("Hello World");
42Tokyo1期生 syamashi です。わずかな才能たよりに、情熱もって学習している畜生。
◆プログラミング歴
2019 11月 atcoderで産声あげる（c++） https://atcoder.jp/users/merhorn
2020 2月 piscine参加（c言語）（Lv9.10突破/多分上位20%ほど）
2020 4月 a
[CodeQUEEN 2024 予選 ABC358] G - AtCoder Tour
[Q] G - AtCoder Tour
コンテスト終了時点でFastestCodeでした！
BFSでO(HM)の解法です。難しいことはしてません。
考察
1. KがHMより大きい場合、最大値のマスでひたすら待機をすることになりそう。
2. 毎ターン最大値max_Aを獲得できれば理想解を得られる。これを前提と考えると、
3. A -= max_Aとすれば、マスを損失値として管理できる。
4.
[ABC353] G - Merchant Takahashi
[Q] G - Merchant Takahashi
2年に1回くらい見かけるConvex Hull Trick。拾えてうれしい。
考察
0. DP[index][今いる町] = 最大益
のDP[N][N]テーブルを使えば、答えはDP[N-1][0 ~ N-1]の最大値で求まる。
ところがO(N^2)でTLEしてしまう。どうにか高速化する必要がある。
初期値を考える。
まず町0にいるとしてD
[ABC353] E - Yet Another Sigma Problem
[Q] E - Yet Another Sigma Problem
考察
0. Sが最大3e5文字の文字列が来るんだけど、なんと|S|の総和も3e5。
0. 1文字ずつ考えたとして、O(|S|log|S|)が間に合う。
1. とりあえず受け取った文字列を昇順にsortする
2. S="abcd"があった場合。
・1文字の"a"がどれだけ合致しているかを考える。
it = lower_bound(
[ABC350] F - Transpose
[Q] F - Transpose
本番出れていないんですが、裏イベントの 第一回マスターズ選手権 -決勝- で遊んでいました。とても良い日で、ごはんも美味しかった。
ABCに出ていた場合、パフォ1600弱で負けです。
考察
1. 直感では()の深いところから処理していくと思ったが、間違い。
どうしても()の文字列をどこかに保存することになり、S^2のデータを扱ってしまうことになる。これは無理。
[ABC214] F - Substrings
[Q] F - Substrings
考察
解説ACした。dp何もわからない…。
0. とりあえず「1個前をとらない」という条件をなくして考えてみることに手がかりがある。簡略化して考える手間を惜しまないほうが、俺にはちょうどいいかもしれない。
1. dp[i]を、index_i番目の文字を採用した場合何通りになるか、で管理する。
2. 答えはdp[0 ~ N-1]の和、のようになるのだがちょっと
[ABC348] F - Oddly Similar
[Q] F - Oddly Similar
考察
O(2000^3)をどうbitsetにしようか、という思考を最初から最後まで考えていた。どうまとめればいいかわからなかった。
解説ACを具体的に処理する。
1. まずj列を固定して考える
2. i(0 <= i < N) 行を探索する。
用意するbitsetは2つで、
tmp: maxA * maxN の二次元配列データ。j列目だけを見た時に、
[ABC348] E - Minimize Sum of Distances
[Q] E - Minimize Sum of Distances
考察
1. とりあえず0を根とした場合の、f(0)のスコアを求める。
2. 0の子供1がいて、1に移動した場合のスコアは、なんらかの差分計算で求められそう。何の差分をとればいい？
3. 子供1に近づいた場合、子供1以下のCの総和だけスコアが下がることが分かる。また、逆に子供1に属さない頂点のCの総和だけスコアが上がってしまう。
[ABC348] D - Medicines on Grid
[Q] D - Medicines on Grid
普通にBFSを考える
考察
1. DP[i][j] = マス(i, j)に到達したときの最大エネルギーとして管理するとよさそう。
2. 薬を入力するときに、DP[i][j]に薬の値をいれてみる。
3. 最大値の更新があったときに進む、だけだとうまくいかない。
入力で受けた薬マスに入らない判定になってしまうので、到達したかどうかの判定seen[
[MC Digital プログラミングコンテスト2024] AHC031
暫定57位->システス58位でした。
https://atcoder.jp/contests/ahc031/submissions?f.User=merhorn
ペナルティが2種類あって
1. 予約面積に足りない場合はarea_cost * 100のペナルティ
2. パーティションを消す/設置する場合は、距離のline_cost * 1がペナルティ
明らかに1.が重たいので、最初の目標はare
[ARC173] B - Make Many Triangles
[Q] Make Many Triangles
考察
1. N <= 300と少ない。O(N^2)くらい計算できる
2. 同一直線上にある点集合Xと、そうじゃない点集合Yがわかればうれしい。
3. Xの3点を結んだ3角形は直線になってしまうからいけない。どこか1つでもYの点を組み合わせれば3角形が作れることが分かる。
4. Xの最大数を求めたら、YはN - {Xの個数}で求まる。
5. 答えはm
[ABC343] F - Second Largest Query
[Q] Second Largest Query
全然わからなかった…。これ1600人解けるのすごいね。
俺はACL使っていないのでテンプレートを調整してます。
考察
・セグ木を魔改造すればよさそう
・どんな値を持てばいい？
-> {max, max_cnt, 2nd_max, 2nd_cnt}の4要素で管理すればいい
・2つを統合するときには、上位2つの値と個数を調べる。
実装
////