AtCoder Regular Contest

ARC133B 拡張したLIS.類題: 問題:ARC126B， 記事実装 \(P\) のindex を回した方が楽． 倍数判定なので，エラトステネスの篩と同様にできるため． \(Q\) のindex を回すと，約数を列挙しないといけないとので， \(O(N^{\frac{1}{2}})\) が余分にかかる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; vll p(n), q(n); cinv(p); cinv(q); vll inv_q(n…

ARC122B \(x \in \mathbb{R}\) であるから，範囲を狭くしたい． min を外すため，大小で場合分けする． 場合分けの境目の値が候補になりそうで， 実際にそうなる． これで候補が \(N\) 個に絞れたので全探索できる． 実装\(a\) の中に同じ値が複数ある場合に注意． \(for \ i \in N\) を動かしながら， 今までの \(a_{i}\) の個数 今までの \(a_{i}\) の和 を保持する． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main(…

ARC124B 2つのvector に対して，次は同値． ある並べ替えで一致 multiset として一致 ソートしたvectors が一致 よって， \(x\) を固定したとき， \([a_{i} \oplus x ]_{i \in N}, \ b\) が multiset として一致していれば良い． \(x\) の候補は \(a_{0} \oplus b{j} \ (j \in N)\) のみ． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n…

ARC120B \(k\) を固定する． \(k = i+ j\)となる (\(i,j\)) の組は同じ色で塗るのが必要． 逆に十分であることもよい．例えば，以下の様にグリッドを類別する． 0から8まで移動するとき， パスによらず 0から8のマスをそれぞれ一度ずつ通る．0 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 左上と右下のマスが塗られていない場合に注意． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll h,w; ci…

ARC106B 連結成分毎に考えてよい． 連結なグラフで考えるとき，まずはtreeで考えるとよい． Spannig treeを用いて，treeの場合に帰着できるケースも多いし， まずtreeで解けないと，一般の場合は話にならない． また，操作の性質として，操作によって値の総和が不変であることが分かる． Treeで考えると，葉から値を決めていけばよい． もしtreeのvertex が2個以上なら，最後に2箇所だけ値が定まってない状態になる． このときに，+x, -x の形になっているのが，条件を満たす必要十分条件． つまり，vertex に書いてある値の和が0であることが必要十分． これは，ve…

ARC108B fox の文字が全て異なっているので楽． s を先頭から調べていき，スタックに積んでいく． スタックの方で後ろ3文字がfoxになったら消せばよい． O(N)で解ける． 実装は，スタックでなくvector で行った． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; string s; cin >> s; string t; rep(i,n){ t.push_back(s[i]); ll x = t.length(); if(x >…

ARC109B まででなく， と が入っているのが気になる． まず，丸太の買い方として，同じ値段なら長いほうが得． 言い換えると，短いほうで出来るなら，長いほうでも出来る， いわば上位互換． 上位互換の考えは，貪欲法を示すときによく使う． 大きい方から買うので， を買う． 買い方の次に考えるのは切り方． 買った丸太のうち，切らないでそのまま使えるものは使ったほうが良さそう． 実際，その考えで正しい． 買った丸太のうち短い方から，分割の仕方を決めていく． 長さ の丸太をもし切るのなら，もっと大きい丸太の中から， 長さ のパーツを切らないといけない． その2つを取り換えれば，長さ の丸太を切らずに…

tokuminiさんのAtCoder Regular Contest 155での成績：1022位 パフォーマンス：445相当 レーティング：1893→1807 (-86) :( https://atcoder.jp/users/tokumini/history/share/arc155?lang=ja A問題に全ての時間を投入して13WAで0完。Ratedコンテストでは自己ワーストのパフォーマンスだったらしい。 成績表 茶色パフォーマンスという括りで見ても、2017/07/23以来らしく、5年半ぶりか。 マイナス幅としてもワースト。こういうことも起こる。 A問題 解説に近いところは考えるんだけ…

01/16(月) 午後4時起床。30分近くかけて布団から這い出てインターン先の定例会・勉強会に参加した。 先週の進捗は、金曜日の1on1でこの1週間何をするか決まったということのみ。まだ手を付けていない。簡単な修正なので、今週金曜日にある次の1on1までに終わらせることを期待されている。それくらいはさすがに達成したいものだ。 勉強会はKaggleの参加記だった。最近終了したコンペでめちゃくちゃ良い順位を達成されたらしい。機械学習は使わなかったとのこと。そして、機械学習を使わない解法が強いコンペだということが、順位表の上にいるチームの顔ぶれから分かりやすかったということが語られていた。競プロで順…

tokuminiさんのAtCoder Regular Contest 154での成績：907位 パフォーマンス：1356相当 レーティング：1938→1891 (-47) :( https://atcoder.jp/users/tokumini/history/share/arc154?lang=ja 3ヶ月ぶりの水色パフォーマンス。 今回のコンテストは、全体的にサンプルが少なくて自分でちゃんとあらゆるケースを想像しないといけないものだったので、苦手なタイプではあった。 A問題 和が一定な2つの数で掛け算を最小化したい場合、差を一番大きくした方が良いというの、なんか常識というかそんな感じで知っ…

01/09(月) 午後2時過ぎ起床。半から指導教員の先生が海外の先生とオンラインでミーティングをするのに同席させてもらった。 かなり辛かった。話の流れでこういうことになったはいいが、あくまで先生の専門であって自分が今勉強しているグラフ理論からは微妙に遠い。事前に頂いた資料もあまり目を通せておらず、理解度が微妙な感じになった。終了時刻が決められていないのも応えた。結局2時間程度で終了。海外の先生が退室されてから指導教員の先生と少し話し、辛うじて理解できた部分について少し質問したりした。 じゃりみちさんのゆっくり実況シリーズ「ありきたりな惑星緑化」の最終回が投稿された。このシリーズは最初から最後ま…

2023/1/14に開催されたAtCoder Regular Contest 153に参加しました。 atcoder.jp 前回のARC152では、高難易度のB問題が解けてくれて、レートが大幅に上昇という結果でした。 ARCは問題セットとの相性で大分結果が違ってくるという印象なので、今回もどうなるかわかりませんが、とりあえず今回は２完目標で臨むことにします。 Rated参加します。今回は２完以上が目標。がんばります✊AtCoder Regular Contest 153 - AtCoder https://t.co/jSIMF5i6r8— devgenjin77 (@devgenjin77) …

A,C問題を解いて2完。 tokuminiさんのAtCoder Regular Contest 153での成績：475位 パフォーマンス：1911相当 レーティング：1910→1910 (±0) :| #AtCoder #ARC153 https://atcoder.jp/users/tokumini/history/share/arc153?lang=ja A問題を通したあとB問題で時間がかかってしまい、途中で順位表を見たときに解いた人数が多すぎてこれ解けても順位が伸びないと思ったのでCに取り掛かっていた。Cも解けなかったら悲惨なことになっていたのでなんとか通せて良かった。 A問題 制約的に…

https://kenkoooo.com/atcoder/#/contest/show/28c6016e-1df1-4039-aeee-95f2777bd5ac ■01. D - Harlequin(CADDi 2018 for Beginners) https://atcoder.jp/contests/caddi2018b/tasks/caddi2018_b ・取りうる状態を考える 状態A：すべてのりんごが偶数個 状態B：どれか１つのりんごが奇数個 終了状態はA(all0) 状態の変化はA->B,B->{A,B} Aの状態を相手に渡せば真似っ子戦略を行い 常にAの状態で相手に手番を渡せる。…

2022年に自分がやっていたことを書きます。こういうのを書くときに Twitter をやっていると思い出しやすくていいですね。Twitter によると今年一年でやっていたことの8割はゲームなのでゲームの話をします。結構長くなってしまいました(約6000字)。 1月年始は逆紅クイズにハマっていたようです。そこそこ自信作です、ぜひ解いてみてください。 問題ID：naimono https://t.co/Afg7DhgPfI #逆紅クイズ #逆紅クイズ新作問題 初めて作りました 難し目かも?(検索はご自由に) — ふもふも (@fumofumofuni) 2022年1月10日 後半は wordle …

フローの問題を履修しているときに出くわしましたが、解説とちょっとグラフの作り方が違ったので。 解法 葉であるマス目を頂点として同じ行or同じ列どうしの頂点を辺で接続し、フローグラフを構築する。 すると、Sourceを、Destinationをとしたときの最小カットを求めることで、問題の解を求めることができる。 今回はどのように容量を持たせるかというところが問題だが、問題設定的に葉(=頂点)を落とさないといけないので、頂点が容量を持てるとうれしい。 そこで、各頂点をの2つに分割し、他の頂点から接続されるポイントをに集約し、逆に他の頂点へ向かうポイントをに集約する。さらに、の間を容量の辺で接続する…

2022/11/20に開催されたAtCoder Regular Contest 152に参加しました。 atcoder.jp 一か月ぶりのARC。ここ最近のARCでは、問題セットとの相性の良し悪しで、結果が大きく上下するというのを繰り返してきました。実際、前回は1完で爆死という結果でした。 まあ、今回はなんとかレートを上げられるぐらいの結果は残したいなあということで、2完を目標として臨むこととしました。 Rated参加します。久々のARC。とりあえずは2完してレートを落とさないように頑張ります✊AtCoder Regular Contest 152 - AtCoder https://t.co…

工事中 11/14(月) 午後4時過ぎに起床。起きたら生協に行こうと思っていたが、そんな余裕のある時間には起きられなかった。 隙間時間に年末調整を終わらせた。先週金曜日、もとい土曜日朝方に送った質問にはまだ返信が来ていなかったので、待つのを諦めてそれっぽく書いておいた。そもそも自分の判断が合っているか確認する程度だったので、何かミスが発生するとは思っていない。発生しても死にはしない。 年末調整にチャレンジした。期限は11/14つまり来週の月曜日である。少し書類作成が進んだところで、インターンの給料の扱いに関して疑問が生じた。担当の方に質問を送ったが返信は月曜日になるだろう。週記（2022/11…

2022/10/16に開催されたAtCoder Regular Contest 151に参加しました。 atcoder.jp 昨日のABCは所用のため参加できずでしたが、今週はARCがある週。 現在、レートは入水まであと少しというところまで来ているので、ここいらでなんとか水パフォをとって入水を決めようという気持ちで臨むこととしました。 Rated参加します。とりあえず2完以上、そして水パフォをとって入水できるようにがんばります✊AtCoder Regular Contest 151 - AtCoder https://t.co/vw5juBJbhr— devgenjin77 (@devgenj…