YU2TA7KA's BLOG ~take one step at a time~

派生開発、組み込み開発周りのこと。

プログラミング-競技プログラミング

AtCoder Beginner Contest 168 ふりかえり

はじめに A問題 A - ∴ (Therefore) B問題 B - ... (Triple Dots) C問題 C - : (Colon) D問題 D - .. (Double Dots) E問題 E - ∙ (Bullet) おわりに atcoder.jp はじめに AtCoder Beginner Contest 168に参加しました。D問題まで解けて4完、これを継続してい…

【Rust】茶色コーダーに到達【AtCoder】

はじめに モチベーション 面白さ 精進 1. AtCoder Problemsのrecommendを解く 2. 競プロ参考書を読んだり実装したりする(今は螺旋本) 3. けんちょんさんの記事をめっちゃ読む 4. 参加コンテンストの復習(pdf,動画,他者解答の確認) 5. 自分のレベルを把握…

std::mapを使った集約処理

はじめに 実装 使用例 制御の名前 おわりに ちなみに はじめに 競技プログラミングの問題でキーごとに出現回数をカウントするシーンが多くあります。この制御をC++のstd::mapを使って実装します。 実装 #include <map> using namespace std; template <typename K, typename V, typename A> void map_c</typename></map>…

AtCoder Beginner Contest 164 ふりかえり

A問題 B問題 C問題 D問題 おわりに atcoder.jp AtCoder Beginner Contest 164に参加しました。C問題までは解けて、D問題は一時間以上かけてもわからずゲームオーバー。それでもC問題までをWAなくそれなりの速度で解けたため、パフォーマンスが自己ベスト更新…

ダイクストラのアルゴリズムをRustで実装

はじめに BinaryHeapについて 実装 隣接行列を用いた実装 優先度付きキューを用いた実装 参考 はじめに 最短経路を求めるアルゴリズムとして有名なダイクストラ法をRustで実装しました。ダイクストラ法は隣接行列を用いるとO(|V|^2)ですが、優先度付きキュー…

AtCoder Beginner Contest 160 ふりかえり

A,B問題 C問題 D問題 この問題で使えた技 コンテスト中に新しく出せたコマンド おわりに 蛇足 AtCoder Beginner Contest 160に参加しました。Cまでは解けて、D問題がわずか1分のタイムオーバーで非常に悔しく楽しい回でした。 atcoder.jp A,B問題 WAもなくス…

ABC015_C 高橋くんのバグ探しで学ぶstatic mutの危険性[Rust]

要約 問題概要 解法 危険な実装(ダメ絶対) 構造体を使った安全なコード*1 static mut を使った危険なコード 参考 要約 DFS(深さ優先探索)の勉強としてAtCoder Beginner Contest 015 C問題をピックアップ。 グローバル変数を使った解答例を模倣してstatic…

ABC157 C問題のふりかえり

2020年3月16日に開催されたAtCoder Beginner Contest 157に参加しました。C問題が解けず非常に悔しかったです。解説などを見てようやくACし、その中の学びをふりかえっておきます。 【結果】 順位 4126th / 6597 パフォーマンス 411 レーティング 105 → 135 …