記事一覧
[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
[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つの値と個数を調べる。
実装
////
[ARC170] B - Arithmetic Progression Subsequence
[Q] B - Arithmetic Progression Subsequence
考察
0. A<=10と特徴的。何かAに絞って数え上げられないか考える。
O(NlogN*10)くらいでいけそうだと思う。
1. index_iを0~N-1まで見るとして。数列の末端をindex_iに固定して考える。
2. 等差数列のパターンを出してみると、どの数も4~5通りしかないことに気づく。
//
[ARC170] A - Yet Another AB Problem
[Q] A - Yet Another AB Problem
考察
1. どうしても作れないケースを考える。
サンプル12S:ABT:BA1. Sの先頭をBにしたいけど、先頭より前でAに変えるような場所がないのでできない。2. Tの末尾をAにしたいけど、末尾より後でBに変えるような場所がないのでできない。サンプル26S:BBABAAT:BBBAAAこれもできない。1. S[2]をBにしたいけど
[AGC065] Shuffle and mod K
[Q] Shuffle and mod K
考察
1. permutationで全パターン試す。最善スコアがどのような出力になるかを観察する
sample K=1033:3 1 9 8 626:2 1 9 840:2 1 0 6 5 230:0 5 1 0 1 030:0 1 0 5 1 070:7 6 5 2 11. 数がばらけている場合、降順のかたまりが1or2つできてる2. 同じ値が複数
[ABC331] F - Palindrome Query
[Q] F - Palindrome Query
考察
0. 回文を高速に判定する技あるかな？何も思いつかない。トリッキーな工夫の余地がないように見える。
ものすごく単純に「文字列Sの切り出しと、逆さ文字列Tの切り出しが同一か比較する」を回答する。この方法を軸に高速化できないか考える。
int main() { ll N, Q; string S, T; cin >> N >> Q >