結果 3完(13:39) Rated 1006/4450 コンテストURL 所感 A: 一瞬焦った (A問題に1mmでも思考を要する問題が置かれるとビビる) B: 久しぶりにB問題っぽいB問題が出た気がする ソートして変化点を計算,2以下ならOK C: バグらせて時間を溶かした これくらいならB…
気持ちが良い問題だった 問題リンク 問題概要 N人の宇宙飛行士がいます P個のペアが渡されます ペアは同じ国籍同士の宇宙飛行士の番号です N人の中から,国籍が違う宇宙飛行士のペアはいくつあるか 解説 同じ国籍どうしの宇宙飛行士をDFSやUnionFindでグルー…
結果 3完(10:10) Rated 2109/4713 コンテストURL 所感 A: 問題文の通りに実装を行う B: 一人の監視員で (d * 2 + 1) の範囲をカバーするので、Nを(d * 2 + 1) で割る(切り上げ) C: 数列Aの最大値が2以上含む場合はすべて最大値,そうでないなら最大値の箇…
結果 4完 (3WA) Rated内2484位 (Aの提出者4930人) コンテストURL 所感 A: 隣り合う文字列が同じところがあった場合'BAD' B: 指定した数列を作り、総和から絶対値が一番小さいものを引く C: 包除原理 コーナーケース 1 1 1 1 に注意(30分溶かした) D: Cで悩…
問題概要 問題ページへのリンク N頂点の木がある。頂点ui, vi間の辺の長さはwiとする 同じ色に塗られた任意の2頂点間について、その距離が偶数になることを満たすように各頂点に色を塗る そのような塗り分け方を1つ見つけて出力せよ 考察 偶数同士、奇数同士…
Dに一時間以上費やすも解けず蒸発 とりあえずめっちゃ書いたので供養 ACコードではない #include <bits/stdc++.h> using namespace std; long long const N = 100010; long long n; struct edge { long long cost, to; }; vector<edge> G[N]; vector<bool> F(N); // true: even vector<bool> C</bool></bool></edge></bits/stdc++.h>…
問題概要 問題リンク 1, 10, 100, ..., 109, 5, 50, 500, ..., 5 * 109円硬貨がある スーパーでN種類の果物が1つずつ、それぞれA0,A1, ..., An-1円で売られている N種類の果物のうち、K個買う時の合計金額をちょうど支払うために必要な硬貨の枚数の最小値を…
躓いたのでメモ 問題概要 問題リンク 各頂点にお金が割り振られた無向グラフが与えられる 始点は自由で、より多くのお金を獲得したい、ただし同じ頂点は1回しか通れない 考察・解法 各頂点からそれぞれDFSして最大値更新すればOK~~~と考えたが、入力例1で不…
以前解説ACしたものを自力で解いた 問題概要 #, .のみで構成されるグリッドにおいて、#と.を交互に渡る経路はいくつあるか ただし始点は#, 終点は.とする 解法 DFSとUnion Findで.と#で交互に渡ることのできるエリアをグループにする 以下は入力例1の場合 #…
一日溶かした 問題概要 atcoder.jp スタートとゴールそれぞれのマスを含んだ迷路が与えられる 入力例5 7 8 .#...... S#.#.### ...#.#.# ###.#.G. .....#.. ..##.#.# ........ 入力のままだとSからGには到達できない 一つの#を.に変えることでSからGに到達が…
はじめに 唐突だが私は携帯を変えるごとにバックアップは取らず、写真は全部消去するタイプだ そろそろ携帯を変えよう考えていたところ、自分にとって一大イベントがあったことを思い出した 写真を消去してしまうのはもったいないと思い、ブログに写真を残す…
結果 4完(3WA) Rated内209位 コード atcoder.jp 所感 Bでテストケースが合わず焦る Cで同じ色だったら消すと勘違い Dで島の親が同じだったときの処理を考えない こんな感じで結構ミスしたと思うんですけど、4完できたので自分としてはよくやったなと称えたい…
負数にする系(主語がでかい) 問題リンク 問題概要 チームの解答問題数、ペナルティ数が与えられる 上から番目にはいくつのチームが当てはまる可能性があるか 考えたこと ※以下出てくる用語はC++の用語として記載します 連想配列mapを用意する key: 解答問…
最近読んだ本 「優しい死神の飼い方」を読んだ 以下公式サイト*1より抜粋 犬の姿を借り、地上のホスピスに左遷……もとい派遣された死神のレオ。戦時中の悲恋。洋館で起きた殺人事件。色彩を失った画家。死に直面する人間を未練から救うため、患者たちの過去の…
最近闇雲に精進していて良くないなと感じたので目標を立てる 2月はグラフ問題を徹底的に行うことにする カテゴリー別に分類している以下のページの問題を増やしていきたい ozikot.github.io
問題 No.583 鉄道同好会 解法 オイラーグラフというらしい UnionFindで特急列車でいける駅の連結を判定 駅から直接いける駅数が奇数の駅が2以下ならYES(一筆書きの始点と終端) コード #include <bits/stdc++.h> using namespace std; struct UnionFind{ vector<int> par; UnionFi</int></bits/stdc++.h>…
経緯 敬遠していた,グラフ問題に対する有効的で基礎的なアルゴリズムであるdfs(depth-first-search)の苦手意識の払拭のため練習を行うことにした 解いた問題 ABC054 C - One-stroke Path 頂点1を始点とした全頂点経由経路の数を求める ABC075 C - Bridge 連…
研究のこと 今自分が担当してる部分が全体のうちのかなりの大部分を占めており, 自分なりに勉強して試行錯誤していたところ,完全上位互換の方がバックに控えてると知り, あんまり信用されてないのかなと色々推察してしまいました もう少し頑張ってみよう…
所感 再帰関数に手こずった 解法・コード github.com おわりに 練習量を増やす
結果 コンテストは2018-12-08(土)に開催 3完 所感 コンテスト時はDが異様に難しく感じて解けなかったが今日解説を見て解いた 細分化して問題を解くことに慣れたい 解法・コード github.com おわりに 今日は誕生日だった 進路はもう院進で固まってきた 今はま…
読んだ本 右上から時計回りに 余命10年 [小坂流加] 358ページ 終電の神様 [阿川大樹] 320ページ あした世界が終わるとしても [櫻木優平] 176ページ 私は存在が空気 [中田永一] 291ページ 読書を始めたきっかけ Twitterにてツイートの文章を考えるときに、自…
結果 激遅3完 所感 Bで少し悩んでタイムロス Cで無限に悩みタイムロス DはDPかな…と考えてた レート推移 下がり続けるレート 解法・コード github.com
経緯 先日出題された AISing Programming Contest 2019 のC問題, Alternating Path を深さ優先探索で解きました atcoder.jp グリッド探索…空で書けないな…と痛感したので,まずは幅優先探索だと思い(?) 行動に移しました 解いた問題 ABC088-D「Grid Repa…
昨年 昨年,2018年の11月にAtCoderで競プロを始めてから一年が経ちました 灰色から緑色に遷移することができました 今年 2019年は 水色になること 院進か就職するか自分が納得して決断すること を目標に頑張っていきたいです
コンテストには出られなかったのでA, B, C問題を解いた 所感 C問題のグリッドでDFSを無限にバグらせた グリッド問題を解いていきたい 解法・コード github.com
結果 激遅2完 所感 B問題が解けなくて血の気が引いた 泣きながらC見てたら運良く解けた 解法・コード A,B,Cの三問書いたので是非見てください github.com