AtCoder Beginner Contest

ABC288C DFSをして，すでに到達している頂点に到達したら， その辺はサイクルを作っているので除く辺となる． 同じ辺につき2回カウントするので2で割る． この様な辺は，(向きも考慮するとき)後退辺と呼ぶらしい？ DFSにおける頂点，辺 dfs(cu, pa){ // >>> // *** [頂点]に関する処理 (入ってきたとき) // <<< for(ne : to[cu]) if(ne != pa){ // 必要ならifをつける // >>> // *** [辺]に関する処理 (出るとき) // <<< dfs(ne, cu); // >>> // *** [辺]に関する処理 (出ると…

ABC287 A~Dの1000点． D問題先頭から調べるのと末尾から調べるのは， 同様の操作になるので関数化できる． \(s[0,i+1)\) と \(t[0,i+1)\) がマッチするのは， \(s[0,i)\) と \(t[0,i)\) がマッチするかつ \(s[i] = t[i]\) または \(s[i] = ?\) または \(t[i] = ?\) であることと同値． 空文字列同士はマッチする． E問題試験後に解説を見てAC. 各 \(k\) に対して，答えが \(k\) になる \(i \in N\) を再帰で求める． 先頭 \(k\) 文字が一致しているという2項関係で\(N\) …

結論から言うと、クエリ平方分割で O(N√Q log(max {A}) + Q(√Q + logQ)) で解けます。 問題概要 atcoder.jp 考えたこと クエリ 1 が曲者で、通常の遅延セグメント木には乗せられないため、仕方なく「困ったときの平方分割」をしてみる。 √Q 回のクエリを 1 ブロックとしてまとめると、クエリ全体として √Q 個のブロックがあることになる。 したがって、ブロックあたりおよそ O(N logN) くらいに収めることを考える。 前述の通り、1 ブロックあたりのクエリ回数は √Q 回なので、クエリ区間の切れ目も高々 2√Q 箇所である。 そこで、高々 (2√Q +…

ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)に参加しました。 結果 A,B,C,D問題の4問正解でした。 もう少しでE問題も解けそうだったから悔しい。 あと、何故かキー入力の調子が悪かった。相変わらず英字のHHKBを使っているけれど記号とFnキーの入力でどこだっけと考える時間が入って思うように入力できなかった。いつもはもう少しスラスラ入力できるのにどうしたんだろう。 A - Range Swap 問題文のとおりに処理する。 数列Aのコピーを用意して、P~QとR~Sをコピーへ移してから出力する。 B - Cat 問題文のとおりに処理す…

AtCoder Beginner Contest 285に参加しました。 ※いつもと違って日曜日に開催なので翌日の仕事に影響しないようにいつも以上に簡潔に考察の整理 結果 A,B,C,Dの4問正解でした。D問題がいつもより早く解けた気がする。 A - Edge Checker 2 配列で2分木を作るときに親子関係がどうなっているかを知っていればすぐに解ける問題。 子の番号は親の番号2と親の番号2+1になるのでa,bの関係がこれに当てはまるかどうかを判定する。 B - Longest Uncommon Prefix 問題文を読んでもいまいち何をすればいいかわからなかった問題。 入力例とその解説を…

ABC284D \(N = p^{2} q \leq 9*10^{18}\) と \(N\) が大きいが， 素因数の最小値は小さい． (重複を許して)3つの素因数があるので，どれか一つは\(N^{1/3}\) 以下． よって， \(min(p,q)\) のうち，一方は全探索で求まる． \(p,q\) の一方が求まれば，もう一方も求まる．クエリ問題なので，使われる素数を前計算して使いまわしたが， \(T \leq 10\) だったのでクエリごとに計算しなおしても間に合う． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23…

AtCoder Beginner Contest 284に参加しました。 結果 A,B,C,Dの4問正解でした。 E問題ももう少し時間があれば解けそうな気がした。ぱっと解き方を思いつかなかったから先にF問題解いてみたのが失敗だったな。 A - Sequence of Strings 問題文の通り処理する。 配列に文字列を登録してから逆順に表示すれば良い。 文字列はN個とわかっているのでインデックスをNから1まで順番に減らしていけば良い。 配列の扱い方がわかっているかどうかな問題だと思う。 B - Multi Test Cases これも問題文の通り処理すれば良い。 具体的には以下の処理をT回繰…

01/30(月) 午後2時に一瞬起きて修論発表会のZoomに接続した。もともと可能なら参加するようにと指導教員の先生に言われていて、特にこの時間帯は基礎論の発表だったから無理して起きてみた。しかしやはり無理だったようで、接続はそのまま放置して布団に戻り二度寝した。 次に午後4時半ちょっと前に起床しインターン先定例会に参加した。先週は集中講義を理由に何も稼働していないが、そもそも先週の進捗報告にも出席していないため、先々週少しばかりコードを修正した分の報告が残っていたのでそれを発表。 勉強会は二値分類の精度指標の話だった。F値という指標は二つの指標の調和平均で定められておりなんだか複雑そうな形を…

AtCoder Beginner Contestの過去問から、その提出コードの解答例です。 AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。 atcoder.jp プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。 「競技プログラミング」を略して、「競プロ」などと呼ばれています。 #B - Qualification Contest atcoder.jp僕が作成、提出したコードは、以下のとおりです。 /* AtCoder Problems in C++ #B - Qualification Con…

6完99:44 210位 D通したのギリギリすぎるけど、なんとかイベント圏内には入った こんなにたくさんの暖色どこに隠れていたんだ... A Many A+B Problems いつもの、足すだけ 「実はオーバーフローします、ペナするやつは決勝にお呼びじゃないよ～」 みたいなのあるかと思ったけど、そんなことはなく (AC 1:19) B Qualification Contest こうなってしまうとAにあってもよさそう 先頭K個だけ取り出して、sortすればおわり (AC 2:54) C Don't be Cycle またサイクルだ～ 連結成分ごとに(辺の数) - (頂点の数) + 1なので、…

特に理由があるわけではないがふと久しぶりに挑戦してみたくなったため、2/4開催のAtCoder Beginner Contestに参加してみた。 atcoder.jp 結果としては正直あんまりで、C問題すら解けずレーティングを下げることになった。 atcoder.jp これまではただ問題を解いてそれで終わりだったが、せっかくなのでちゃんと解説まで読んでみようと思い改めて内容を確認してみた。ただ結構難しい。。 C問題の解説はなんとなく理解できたが、D問題は正直解説を読んでもあまりうまく理解できていない。 atcoder.jp atcoder.jp と思ったら今回のD問題はランク的には結構難しいら…

2023/2/4に開催された、Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)に参加しました。 atcoder.jp 告知情報によると、今回のABCはD以降の難易度が高めということみたいですが、あまり細かいことには拘らず、今回も５完以上を目標として挑むこととします。 https://atcoder.jp/posts/974?lang=ja Rated参加します。今回はいつものABCと毛色が違うみたいですが、いつもどおり５完以上目標で頑張ります。Toyota Programming Contes…

競プロについての活動記録を毎月とってみようと思います。 これをやる理由は 競プロのモチベーションアップにする 記録しておいたらもしかしたら後で何かの役に立つかもしれない 何か記事を書く癖をつけたい という感じです。 もしかしたら今回しかやらないかもしれません。この記事を書きながら数回前のコンテストについてけっこう覚えてないなと思ったので、当時思っていた感想とは異なるものもあるかもしれません。 AtCoder のレート変化 1658 → 1607 (-51) レートが上がることの多い ARC にだけ Rated 参加したが、すべてレートが下がってしまった。 もう水色に落ちたくないなと思っていたけ…

6完41:05 234位 G解けたと思って40分バグらせたのかなしすぎる A Majority もうforのあるAにも慣れてしまった、数えるだけ (AC 2:16) B Postal Card 下3桁しか見なくてよいので、あらかじめ余分なところを落としてしまいます そしたらただ一致判定するだけ (AC 5:03) C Path Graph? これこわい とりあえず、N-1=Mでないといけないのはいいですが、変な形になっていないか確かめる必要があります もっと楽なやり方ありそうだけど素直に ・次数が1のもの2つ残りは2 ・全体が連結である をそれぞれ判定しました (AC 13:28) D Mat…

AtCoder Beginner Contestの過去問から、その提出コードの解答例です。 AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。 atcoder.jp プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。 「競技プログラミング」を略して、「競プロ」などと呼ばれています。 #B - Cat atcoder.jp僕が作成、提出したコードは、以下のとおりです。 /* AtCoder Problems in C++ #B - Cat https://atcoder.jp/contests/abc…

AtCoder Beginner Contest 287 の振り返り A問題 方針 解説から B問題 方針 解説から 二分探索を活用する C問題 解説*1から D問題 方針 解説*2から AtCoder Beginner Contest 287 の振り返り A、B問題を解くことができた A問題：数え上げ B問題：数字を文字列として扱い比較した。文字列の切り抜きについて調べる C問題：グラフ問題と見て即座にD問題に移った。しかし、一度探索したノードを再び探索した場合にNoとなるだけでは、と考えた D問題：愚直に実装したが14のテストケースでTLEになった 文字列の切り抜きに苦戦した 添字の単純な…

コンテストページ: https://atcoder.jp/contests/abc287 コンテスト中AC: A〜E C - Path Graph? D - Match or Not E - Karuta C - Path Graph? パスグラフのとき、両端の次数は1で、それ以外は2です。また、連結成分の数はただ1つになる必要があります。 以上から、以下がパスグラフである条件です。 次数1の頂点がちょうど2つ存在し、その他の頂点の次数は全て2 連結成分がただ1つ 上は、次数をカウントしていくことで判定でき、下はUnion Findにより、判定できます。 実装: Submission #383…

2023/1/28に開催された、ユニークビジョンプログラミングコンテスト2023 新春(AtCoder Beginner Contest 287)に参加しました。 atcoder.jp 先週はABC、ARCと立て続けに残念な結果になってしまい、レートの方は1100台を切ってしまう状態に。。 今回も負けを喰らうと、4桁レート維持も厳しくなるかというところ。ここいらで連敗を止めようという気持ちで臨む事としました。 Rated参加します。５完取って、先週の負けを取り戻せるように頑張ります✊ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 28…