日本語によるプログラミングコンテスト
https://atcoder.jp/contests/abc435/tasks/abc435_e範囲を覆うので木を利用したいですが、単純にSegment Treeを使うと空間が大きすぎて無理ですし、自力で木を作ると変な入力(1 1、2 2、3 3、…)にも対応しないといけないので平衡木にしなければならずコーディングが難しいです。 クエリーはそんなに大きい数ではないので、その端点を集めてソートして、その点同士の間の範囲を葉にしたSegment Treeを考えればよいです。 // Cover query #![allow(non_snake_case)] use std::cmp::{min, …
https://atcoder.jp/contests/abc435/tasks/abc435_d黒いノードをいちいち探していたら、そのたびにO(N)かかるので、間に合いません。 そうでなくて、黒くするたびに逆に辿っておけば、合計でO(N)しかかかりません。 // Reachability Query 2 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); s…
0.はじめに 1.ルールの再利用（本番230位相当） 2.ルールの再利用を行い、BFSで既存のルールがあるものを優先する（本番237位） 3.市松模様（2マス1セットでの移動）と再利用マス（内部状態はmodで移動方向管理）（本番94位） 4.市松模様：ルールの配置を効率的に再度割り当てる（本番83位） 5.市松模様：modでの割り当てをやめる（本番79位） 6.終わりに 0.はじめに はじめまして、もしくはお久しぶりです。競技プログラミング歴5年11か月のかえでです。 これは、2025年11月7日金曜日19時から11月17日月曜日19時までの約10日間開催された「HACK TO THE FUT…
AtCoder Beginner Contest 435に参加しました。 結果 A, B, C, D問題の４問正解でした。 E問題難しい… セグメントツリーを使って解く問題かなあと思いつつ、ライブラリは用意してなかったからAtCoderのライブラリを探して来て使えるようにして、セグメントツリーの使い方を調べてってやってたけど導入が難しすぎて諦めた。 しかも解説をちらっと見てきたらセグメントツリーを使う問題ですらなかった… A - Triangular Number 整数Nが与えられるので1からNまでを足した数を答える問題。 を覚えていれば簡単に解ける問題。 覚えてなくてもループ処理で順番に足し…
5日目の記事に戻る こんにちは、ゆーてぃーです。今回は「ゆーてぃーのAtCoder精進【6日目】」ということで、2014年12月6日に行われたABC016のC問題を解きたいと思います。 ゆーてぃーのAtCoder精進 Advent Calendar 2025 問題 C - 友達の友達 問題ページ 問題文 高橋くんはSNSの管理者をしています。このSNSではユーザ同士が友達という関係で繋がることができます。高橋くんはそれぞれのユーザの「友達の友達」が何人いるかを調べることにしました。友達関係が与えられるので、各ユーザの「友達の友達」の人数を求めてください。ただし、自分自身や友達は、「友達の友達」…
◆ はじめに この記事は モノグサ Advent Calendar, 6 日目の記事です。モノグサ社員が「未体験への挑戦」をテーマに多種多様な記事を書いておりますので、併せて見ていただけると嬉しいです！ qiita.com こんにちは、こなです。このブログを更新するのも大変久々で、2023/4/11 に公開した入社記事以来となるようです。今でも入社記事で書いた モノグサ に所属し続けており、日々楽しく開発をしています。 社会人になって競プロから離れた人みたいになっていますが実際には毎週欠かさずAtcoderのコンテスト(ABC, ARC)には参加しており、青水の境界を徘徊する村人と化していまし…
https://atcoder.jp/contests/abc434/tasks/abc434_e異なるウサギが同じ位置に行けると問題が生じるので、グラフにすればいいとわかります。入力例1なら、ウサギはそれぞれ3と5、-1と5、-1と9なので、3 - 5 - -1 - 9というグラフになります。そして、エッジがウサギで、エッジごとにどちらかのノードを取って取れる最大のノード数は、入力例1のように木なら順番にたどればいいので、ノード数-1となります。ループがあるなら、これも順番にたどればノード数になります。ループからひげが出ていても同じです。なので、グラフを連結成分に分割して、それぞれのグラフが…
問題atcoder.jp色 \(1,2,\ldots,N\) があり、各色 \(i\; ( 1\leq i\leq N ) \) について、色 \(i\) の地点が \(A _ i\; ( \geq1 ) \) ヶ所あるとする。また、色 1 の地点を 1 つ固定し、その地点を始点かつ終点とする。その後、色が異なる地点への移動を \(T\) 回行って始点から終点へ移動する方法の個数を求める問題である。予備知識atcoder.jp結局この記事の解法は、noimi さんのユーザ解説の解法を既に体系化された理論で捉え直しただけである。途中からユーザ解説と全く同じ解法になるので、先に見るとよいかもしれな…
4日目の記事に戻る こんにちは、ゆーてぃーです。今回は「ゆーてぃーのAtCoder精進【5日目】」ということで、2015年12月5日に行われたCODE THANKS FESTIVAL 2015 オープンコンテストのC問題を解きたいと思います。 ゆーてぃーのAtCoder精進 Advent Calendar 2025 問題 C - 集合写真 問題ページ 問題文 ある研究室には人の学生がおり、この度写真撮影のために一列に並ぶことになりました。 撮影会場には現時点で人の学生がおり、身長が低い順に左から右へと並んでいます。 1 人の学生は寝坊したため、急いで撮影会場に向かっているところです。 カメラマ…
3日目の記事に戻る こんにちは、ゆーてぃーです。今回は「ゆーてぃーのAtCoder精進【4日目】」ということで、2016年12月4日に行われたABC048のB問題を解きたいと思います。 ゆーてぃーのAtCoder精進 Advent Calendar 2025 問題 B - Between a and b ... 問題ページ 問題文 非負の整数 と、正の整数が与えられます。以上以下の整数のうち、で割り切れるものの個数を求めてください。 制約 入力 入力は以下の形式で標準入力から与えられる。 出力 以上以下の整数のうち、で割り切れるものの個数を出力せよ。 ゆーてぃーの解法 で割り切れるものはずつ増…
qiita.com
note.com
findy-code.io
qiita.com
www.slideshare.net
qiita.com
chokudai.hatenablog.com
qiita.com
qiita.com
