日本語によるプログラミングコンテスト
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_acこれもDPですが、一つ前とその前で最大を覚えておくとよいです。 手元では、 (a, b) = (max(a, b), a + c) が通ったのですが、AtCoderではダメでした。 // Taro's Vacation #![allow(non_snake_case)] use std::cmp::max; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); st…
はじめに AHC017（AtCoder Heuristic Contest 017 THIRD プログラミングコンテスト 2022）お疲れ様でした。念願の初青パフォをキメて入水できたので私にとっては大満足のコンテストでした！ 今回の問題ではスコア計算の重さに苦しめられた方が非常に多かったようですね。それでも上位勢の方々は代表点の選定やスコアの差分計算など様々な工夫を凝らして山登り法や焼きなまし法をうまく適用していたようです。 しかし悲しいかな、私はしがないアルゴ茶コーダー。高速化の勘所なんて分かりません。そこで今回は思い切ってスコア計算を完全に放棄してみました。 本記事ではスコア計算を一切せず…
AHC017 最終50位(暫定49位: 40.3G / 50.0G)の解法 THIRDプログラミングコンテスト2022(AHC017)の解法と，約一週間のコンテスト期間のアプローチについて解説(というか記録)しておきます．ヒューリスティック系コンテストの初心者・中級者や未来の自分の役に少しでも役立てばと思います． 問題の概要 N地点と，各地点を結ぶM個の道があります．この道のいくつかを補修工事するのに通行止めする必要がありますが，そうなると移動が不便になり，不満度が上がります．不満度はある地点から他の地点を移動する際の移動距離が増えるほど大きくなります．工事を行う日数Dと，一日に工事できる(通…
問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要種類のカードがあり，最初，種類目のカードの得点は，枚数は枚である．以下の形式の個のクエリを順に処理せよ． 種類目のカードの得点をに変更 種類目のカードの枚数をに変更 枚のカードを選ぶときの得点の総和の最大値を求める． 解説各ノードに部分木の得点の総和とカードの枚数の総和を持つBinary Trieを作ると，各クエリで処理することができます．サンプル1を例に挙げて説明します．初期状態のBinaryTrieは以下のようになります． 最初のクエリでは，枚使った最大の総得点を求めます． 根の右の子の枚数がであることから左の子のカードを使…
https://atcoder.jp/contests/abc288/tasks/abc288_dにcを加算するとはどういうことでしょう。Aを多項式、すなわちと考えると、を足すことです。つまり、この問題は、の倍数を足して0になるか、言い換えると多項式をで割って余りが0か否かということです。K=3として、をで割って余りを求めると、 となって、K周期だということが分かります。よって、の剰余はで求められます。なので、の剰余をで作れます。これで、各クエリの多項式の剰余をで作れます。 // Match or Not #![allow(non_snake_case)] //////////////////…
0.はじめに 1.問題文 2.最初の考察 3.最初の提出 4.うだうだと考える（実装をする気にならない時間） 5.ローカルでのテストケースを実装して5回目の提出をしました 6.たどり着けない頂点がなくなるまで時間いっぱい山登り 7.順位表のトップが50,000,000,000点!? 8.ライバルには負けたくない 9.天啓が降ってきた（と思ってからの暗黒の3日間） 10.コンテスト8日目（最終日前日） 11.コンテスト最終日（2023年2月5日） 12.終わりに（2023年2月7日更新） 13.最終結果（2023年2月7日更新） 0.はじめに はじめまして、もしくはお久しぶりです、競プロ歴約3年…
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…
前書き なるべく愚直な操作でなんとかする解法です。（実質的には同じかもしれませんが、）mod での累積和を使っていません。 コンテスト中、解法が思いつかずになんとかして無理やり解く方法を考えたもので、綺麗な解法ではないです。 公式解説を読むほうが勉強になると思います。 問題 atcoder.jp 考え方 であれば、左から順に可能な限り0にしていき、0にできない残り個が0になっているかを確かめればよい であるときは、一旦左から順に0にしていったあと、左から 元の数列の値に戻していく ことを考えていく すると、から個については、0ではない値になる 「左から0にする」操作のあと、「左から元の数列に戻…
Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）に参加しました。 結果 A,B,Cの3問正解でした。 D問題がやけに難しかった。一旦おいておいてE問題を解いたほうが良かったかも。 E問題はさっと問題文を読んだ所感だとDPで溶けそうな問題だと思った。 A - Many A+B Problems 問題文の通り処理する。 標準入力でちゃんと数値を2つ受け取れれば困らない程度の難易度のいつも通りのA問題。 B - Qualification Contest これも問題文の通り処理する。 N個の文字列を…
ABC288D とりあえず，クエリは無視して考える.まず \(a_{[i,i+k)}\) の区間全体に \(-x\) を足す．次に \(a_{[i+1,i+1+k)}\) の区間全体に \(x\) を足す．すると，真ん中は変化せず， \(a_{i}\)と \(a_{i+k}\)だけ変化する．とくに， \(x = a_{i}\) として計算すれば， \(a_{i}\) を \(0\) にして， \(a_{i+k}\) に追加した形になる．よって， index が\(+k\)毎に， \(a\) の値をまとめることができる． \(c in k\) に対してまとまった値達が全て等しいことが， 良い数列…
atcoder.jp UnionFindやるだけ、の問題がかなり多いですね。なんとなく感じてはいましたが。 UnionFindした結果得られた最大の連結部分のサイズを M とします。 このとき、これらの M 人は、必ず別々のグループに振り分けられる必要があります。 よって、答えは M となります。 M 未満のサイズの連結部分については、0 ~ M-1 のそれぞれのグループに順番に振り分けていけば問題ありません。 結果として人数が１人のみのグループが作られる場合もありますが、今回の問題にはそういった制約もありません。 public static void solve () { int n = n…
atcoder.jp クエリ毎に、KからX、KからYへの距離の合計を出力します。 ここで、今回与えられるグラフは木です（！）。 よって、任意の２頂点間の経路はただ一つに定められるので、DFS or DFSで探索すれば、 それがそのまま最短経路となります（迂回、合流、分岐は一切存在しません）。 今回は自分が得意なDequeを使ったBFSで実装しました。 public static void solve () { //重み付きグラフを受け取る（隣接リスト） int n = nextInt(), m = n-1; List<List<Edge>> e = new ArrayList<>(); for…
atcoder.jp 解説にもある通り、攻撃１回について、 ・中心の魔物の体力が A 減り、その他は B 減る ではなく、 ・全員の魔物の体力が B 減り、任意の１体のみ A-B 追加で減らせる と考えて、二分探索します。 ここさえ閃ければ、あとは比較的シンプルな二分探索だと思います。 public static void solve () { int n = nextInt(), a = nextInt(), b = nextInt(); int[] hp = nextIntArray(n); //最小のOKを求める問題なので、ngを左側、okを右側に println(binarySearc…
atcoder.jp 自分にはまだ難しかったかな～と思いつつ写経AC。 基本的には、戻り値を呼び出し元に集めていくタイプの再帰の中でも、かなり初歩的な問題だと思います。 個人的に、戻り値が void の再帰しか書けないので、どうにかしてそのように書けないかと悩んでいたのですが、わざわざ効率の悪いやり方を覚えるのもアレなので、観念しました。 では、考察していきます。 ある地点 a[i][j] を始点として、そこから遷移可能なルートの数を dp[i][j] とします。 ちょっと視覚的なイメージになりますが、左上から、各マスに対して再帰をひび割れのように分岐させて、分岐可能なルートの個数を収集してい…
2023/01/23 17時ごろに起きる。 インスタントうどんを作るという時間でもないので、ロールパンを食べてゴロゴロ。気持ちは土曜日 明日明後日の天気が気になるわね。でえ寒波（悟空）の影響で雪が降るらしい。ガッツリ期末試験の日程と被っているので、交通機関が動かなくなった場合大変なことに......。 2023/01/24 12時ごろに起きる。 外出マン。家から出た時は曇っていたのだけど、帰る頃には雪が降っていた。 ファミリーマートでおやつを品定め（滞在時間30分）、購入し、店外を見るととんでもない吹雪になっていた。「出たくね～～～」と思ったけど、店から出ないと帰れないので吹雪の中に身を投じた…
atcoder.jp シンプルな解法としては以下のものがすぐに思い浮かびました。 ・スタート地点から幅優先探索する。 ・探索が終了したら、まだ未探索かつ道であるようなマスを見つけ、再び幅優先探索する。 → 歩数を前回の探索+1にする ・以下、繰り返し しかし、この方法だと上手くいきません。 なぜなら、幅優先探索一回で探索できる範囲（ここでは連結部分と呼びます）について、 連結部分から連結部分への最短距離が探索されていないためです。 具体的には、 ・探索が終了したら、まだ未探索かつ道であるようなマスを見つける の部分が正しくありません。 正確には、前回幅優先探索をした連結部分から、ワープ1回で到…
https://atcoder.jp/contests/math-and-algorithm/tasks/dp_d重さを状態とするDPですね。 // Knapsack 1 #![allow(non_snake_case)] use std::cmp::max; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::…
AtCoderを始めてみようかなと Rebuild.fm 352を聞いていて、AtCoderをあらためて始めてみようかなと。ずっと苦手意識があるんだけれども、ちょっとでも改善したい。 rebuild.fm まずはこのQiitaで紹介されていたものを解いてみるところから始めるか。 qiita.com 書籍として何があるかなと思ったんだけれども、『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』が良さそう。 gihyo.jp
agenda はじめに Write Code Every Dayとは 何を書いてる？ AtCoder Twitter分析 言語処理100本ノック 自分が感じた効果 難しいところ 今後やりたいこと 終わりに はじめに こんにちは。おじろです。 今日は今年に入って始めたWrite Code Every Dayに関して共有しようと思います。 中々良さげなので皆さんもぜひ。 Write Code Every Dayとは 簡単です。毎日コードを書くことです。 自分はこの言葉(?)をソフトウェアエンジニアとしての姿勢と心構え @t_wadaで知りました。 「毎日〜を行う」というのは習慣にしやすいし、自分は…
H は Hadamard transform の H 問題へのリンク 問題 整数 $ N $ と、整数 $ A_1, A_2, \dots, A_K $ が与えられる。 $ 1 \leq M \leq N $ かつ $ d_i \in \Brace{A_1, A_2, \dots, A_K} $ を満たす長さ $ M $ の整数列 $ d $ のうち、 $$ d_1 \oplus d_2 \oplus \dots \oplus d_M \neq 0 $$ となるものの個数を $998244353$ で割った余りを求めよ。 前提 ここではアダマール変換をブラックボックスとして扱うので、定義は無理…
こんにちは。競技プログラミングをしているssaattooと申します。THIRDプログラミングコンテスト2022（AtCoder Heuristic Contest 017）に参加して84位でした。 反省、または誰かの為になることを期待して参加記録を残します。 問題概要 頂点数N、辺数Mの重み付き平面グラフで表される道路網が与えられます。D日間で全ての辺を1回工事（=辺の削除）する必要があります。1日に工事できる道路数の上限はKです。ランダムに日付と2頂点を選んだ時の最短距離の増加分の期待値を最小化してください。 解法 工事日を変更するような焼きなましを書きました。 初期解は連結性と工事数上限を…
放置している ABC - G, Ex を解き進めたい 問題へのリンク 問題 素数 $P$ が与えられる。 $ 0 \leq x \leq P - 1 $ $ 0 \leq y \leq P - 1 $ ある整数 $ n $ が存在して、$ x ^ n \equiv _ P y$ を満たす整数の組 $ (x, y) $ の個数を $ 998244353 $ で割った余りを求めよ。 前提 定義 $ 1 $（原始根） 整数 $ p $ に対し、$ r^0, r^1, \dots, r^{p-2} $ が相異なるような $ r \in (\mathbb{Z} / \mathbb{pZ}) ^ \tim…
atcoder.jp UnionFindを使う問題。 road と train、2つのUnionFindを求めるところまではよいと思います。問題はそれから。 都市 a と都市 b が道路でも鉄道でも行き来できるときとは、以下が成り立つときです。 ・road.root(a) == road.root(b) かつ train.root(a) == train.root(b) このことを全ての都市の組み合わせに対して確かめる場合、計算量が O(N*N) となって間に合いません。 そこで、Mapを使うことで高速化します。 (road.root(a), road.root(b)) を一つの Pair と…
はじめまして、nadareと申します。 普段は機械学習エンジニアとして、レコメンドエンジンの製作や、kaggleやatmacupのような機械学習コンペティションへの参加をしています。 今回はTHIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017）に参加し、全体で126位になりました。 Python3での提出に限定した場合、pretestで3位の絶対スコア、finalで2位の相対スコアだったので、遅いPythonの中では健闘した方だと思います。 本ブログでは自身の解法についての解説と、参加した感想を書いていきます。 overview 除く辺の…
atcoder.jp ダイクストラ法orベルマンフォード法 + 二分探索 というかなり難しいC問題です。 では、解法を整理していきます。 部分点の場合では、SからGまでのルートを全探索して、X=1 のとき間に合うか、X=2 のとき間に合うか…… を検証していくみたいです。部分点の解法に関しては、今回は取り組みません。 満点解法の場合、T の最大値は 10^9 なのでどう考えても間に合いません。 そこで、T をギリギリ超えないような X を探すために二分探索を、 SからGまでの最短距離を高速に求めるためにダイクストラ法を使用します。 二次元グリッド上のダイクストラ法はサンプルがあまりなかったため…
note.com
engineer-lab.findy-code.io
qiita.com
www.slideshare.net
qiita.com
chokudai.hatenablog.com
qiita.com
qiita.com
atcoder.jp
