syamashi
解説とは名ばかり。解けた人が読めばわかる怪文。
ft_printf("Hello World"); 42Tokyo1期生 syamashi です。わずかな才能たよりに、情熱もって学習している畜生。 ◆プログラミング歴 2019 11月 atcoderで産声あげる（c++） https://atcoder.jp/users/merhorn 2020 2月 piscine参加（c言語）（Lv9.10突破/多分上位20%ほど） 2020 4月 atcoder 緑🐢 2020 6月 1stCircle KickOff 2020
[Q] F - Palindromic Expression 気づけばなんてことはなかった！ 考察 0. 素因数分解しちゃだめ！もっとシンプル。 1. A * B * 回文式 * B' * A' が回答の型になることを考える。 2. Nが回文なら回文式だけ出力して終わり。そうでない場合Aを求める。 3. Aの上限は√Nまで。O(√N)で全然間に合う。 4. AとA'が定まったらN->N/A/A'して、Nが小さくなる。 5. 新しいNが回文なら答え。そうでないならBを求める。
[Q] F - Easiest Maze 間に合いませんでした。40分くらい残して初全完がかかっていたのですが残念。 難しいけど、マイルール決めてお絵描きすればいいので、時間をかけて丁寧にやれば絶対できる問題だったなと思う。 考察 1. Noは2パターン a. 最小マスは直下でNマス。K < Nの場合No b. 最大を考える。ルートを変えることで消費マスが2増えるので、N + 2n消費できる。(K - N) % 2 == 1の場合No。 それ以外はYesなので、だいたいYe
[Q] G - AtCoder Tour コンテスト終了時点でFastestCodeでした！ BFSでO(HM)の解法です。難しいことはしてません。 考察 1. KがHMより大きい場合、最大値のマスでひたすら待機をすることになりそう。 2. 毎ターン最大値max_Aを獲得できれば理想解を得られる。これを前提と考えると、 3. A -= max_Aとすれば、マスを損失値として管理できる。 4. BFSで、そのマスに到達するまでの最小損失と最小ターン数をメモする。 5. 解答
[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にいるとしてDP[0] = 0でよい。町1 ~ Nまで無理やり移動すると、 DP[1] = D
[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("b")をとれば、[S, it)の数だけaが合致している。 ・2文字の"ab"
体験談なだけで、科学的な記事ではありません。 虫歯対策になる砂糖を試したくて、フラクトオリゴ糖を始めました。 フラクトオリゴ糖について、明治HPで虫歯にならない簡潔な理由が示されています。ただ、今回フラクトオリゴ生活をした結果、虫歯になる理由があると私は思いました。 実体験 フラクトオリゴ糖生活を2kg試しました。 これが一番安いと思います。 2290円/1kg 食後のココアや、間食のおやつでフラクトオリゴ糖を摂取しました。 確かに口の中が粘つくようなことはありませ
[Q] F - Transpose 本番出れていないんですが、裏イベントの 第一回マスターズ選手権 -決勝- で遊んでいました。とても良い日で、ごはんも美味しかった。 ABCに出ていた場合、パフォ1600弱で負けです。 考察 1. 直感では()の深いところから処理していくと思ったが、間違い。 どうしても()の文字列をどこかに保存することになり、S^2のデータを扱ってしまうことになる。これは無理。 2. 貪欲的にO(S)で処理が求まるしかなさそう。実際そう。 3. 文字がどの
[Q] F - Substrings 考察 解説ACした。dp何もわからない…。 0. とりあえず「1個前をとらない」という条件をなくして考えてみることに手がかりがある。簡略化して考える手間を惜しまないほうが、俺にはちょうどいいかもしれない。 1. dp[i]を、index_i番目の文字を採用した場合何通りになるか、で管理する。 2. 答えはdp[0 ~ N-1]の和、のようになるのだがちょっと違う。 結果的にdp[K ~ K+N-1]の和が答えになる。K個の下準備を施した
[Q] F - Oddly Similar 考察 O(2000^3)をどうbitsetにしようか、という思考を最初から最後まで考えていた。どうまとめればいいかわからなかった。 解説ACを具体的に処理する。 1. まずj列を固定して考える 2. i(0 <= i < N) 行を探索する。 用意するbitsetは2つで、 tmp: maxA * maxN の二次元配列データ。j列目だけを見た時に、どの行とどの行が似ているかを、Aごとに管理。 is_odd: maxN * ma
[Q] E - Minimize Sum of Distances 考察 1. とりあえず0を根とした場合の、f(0)のスコアを求める。 2. 0の子供1がいて、1に移動した場合のスコアは、なんらかの差分計算で求められそう。何の差分をとればいい？ 3. 子供1に近づいた場合、子供1以下のCの総和だけスコアが下がることが分かる。また、逆に子供1に属さない頂点のCの総和だけスコアが上がってしまう。 4. ということは、 子供1以下のCの総和 > 全体Cの総和 / 2 なら、子供
[Q] D - Medicines on Grid 普通にBFSを考える 考察 1. DP[i][j] = マス(i, j)に到達したときの最大エネルギーとして管理するとよさそう。 2. 薬を入力するときに、DP[i][j]に薬の値をいれてみる。 3. 最大値の更新があったときに進む、だけだとうまくいかない。 入力で受けた薬マスに入らない判定になってしまうので、到達したかどうかの判定seen[i][j]を用意すればよさそう。 4. マスに進む条件を次の2つにしてAC。 a
暫定57位->システス58位でした。 https://atcoder.jp/contests/ahc031/submissions?f.User=merhorn ペナルティが2種類あって 1. 予約面積に足りない場合はarea_cost * 100のペナルティ 2. パーティションを消す/設置する場合は、距離のline_cost * 1がペナルティ 明らかに1.が重たいので、最初の目標はarea_costを0にすることにします。 1日目 とりあえず簡単に実装したいと思
[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. 答えはmin(N / 3, Y)になる。 XがたくさんあればYの個数だけ三角形が作れるし
[Q] A. Neq Number BよりもAのほうが難しかったように思う。 考察 0. 数え上げる状況が複雑なので、わかることから詰めていきたい 1. まず何桁になりそうか考える。 1-9: 9通り01-99: 90通り ... 99 - {11, 22, 33, ..., 99} = 90通り。001-999: 819通り ... 0XX は 上の行で求めた90通り。 1XX は 9 * 9 = 81通り。10の位のXには1以外が入
[Q] Second Largest Query 全然わからなかった…。これ1600人解けるのすごいね。 俺はACL使っていないのでテンプレートを調整してます。 考察 ・セグ木を魔改造すればよさそう ・どんな値を持てばいい？ -> {max, max_cnt, 2nd_max, 2nd_cnt}の4要素で管理すればいい ・2つを統合するときには、上位2つの値と個数を調べる。 実装 ///////////// セグ木class RangeMax{public: ll
