コーディングの練習方法 - 備忘録
A free, fun platform for learning modern cryptography Learn By Doing Learn about modern cryptography by solving a series of interactive puzzles and challenges. Get to know the ciphers and protocols that secure the digital world by breaking them. Level Up Earn points by solving challenges. Finish categories to earn trophies and gain levels to track your progress. Can you reach the top of the scoreb
Teachers Summer Camp picoCTF for GenCyber Teacher Program 2024 will be hosted in-person at CMU in June 2024.
この記事について 差分更新型ビームサーチライブラリの実装例について説明します。 差分更新型のビームサーチについては 高速なビームサーチが欲しい!!! などで既に解説されているため、被る部分については詳しく説明しません。 この記事に書いたソースコードをプログラミングコンテストで自由に使っていただいて構いませんが、当ブログは損害などに対する責任を負いかねますのでご了承ください。 前提知識 木に関する用語 深さ優先探索 C++の基本文法 差分更新型のビームサーチとは 木上のビームサーチ、Euler Tour ビームサーチとも呼ばれています1。 ビームサーチは、幅優先探索に枝刈りを取り入れた手法です。探索木における深さ の頂点集合から深さ の頂点集合を生成し、その中から評価値が高い上位 個を選択します。 のことをビーム幅と呼びます。 ビームサーチの例(、赤色が探索中のノード、橙色が採用されたノード
1. はじめに 最初に、本記事ではどのようなトピックを扱うのかについて、少し説明したいと思います。 1-1. 本記事で扱うトピック 21 世紀になり、IT 化が急速に進む今、現実社会ではいろいろなものが最適化されて動いています。これを形作るプログラミングの現場でも、例えば以下のような問題を考えたり、あるいは実際に使ったりすることもあるのではないでしょうか1。いくつか例を挙げてみましょう。 例 1. コイン問題:特定の金額をぴったり支払うために、最小で何枚の硬貨が必要か? 例 2. 最短経路問題:地図上の A 地点から B 地点までに行くのに、最短で何メートル歩く必要があるか? 例 3. 箱詰め問題:長方形の箱に、できるだけ多くの荷物を敷き詰めたい 例 4. 数分割問題:「できるだけ合計の値が近くなるように」2 つのグループに分割したい このように、いろいろな問題があります(もちろん名前を覚
0.はじめに 1.問題の概要 2.放送局1のみを使用し、出力強度を最大にする 3.全部のケーブルをつなぎ全部の放送局の出力を最大にする 4.複数の放送局から受信している家を調べ、電波強度を下げていく 5.電波強度が0の辺を削除する(迷走中) 6.電波強度が0の辺を削除し、放送局1とつながっていないときは再度辺をつなぐ(迷走中) 7.全部のケーブルのつなぎ方を最小全域木にする 8.その先に出力が0より大きい放送局がない不要なケーブルを削除する 9.出力強度を山登りで決定する(迷走中) 10.chokudaiさんに質問してみました(見てほしいところ!) 11.放送局の出力強度を山登りできた! 12.山登りの改善 13.ケーブルの改善 14.初期解の改善。 15.終わりに 0.はじめに はじめまして、もしくはお久しぶりです、競プロ歴3年半のかえでです。 先日、ALGO ARTIS プログラミング
AHC020でシュタイナー木を作るような問題がでました。そこでプリム法ベースのシュタイナー木を作ることがあったのでその方法を説明します。 シュタイナー木とは グラフとターミナルと呼ばれる頂点集合が与えられたとき、ターミナルを全てつなぐ木のことをシュタイナー木といいます。 頂点A,B,Cがターミナル シュタイナー木の例 ターミナルでない頂点はつないでもつながなくても構いません。 シュタイナー木のうちコストが最小のものを最小シュタイナー木といい、これを求めるアルゴリズムとしてDreyfus-Wagner法というものがあるらしいです。しかしこの方法はとても計算量が多いです。 今回紹介するプリム法ベースのシュタイナー木は、計算量は少なくて済みますがコストが最小になるとは限りません。ヒューリスティックコンテストにおける焼きなましの最中など、厳密さより速度が優先されるようなケースでの使用を想定していま
AtCoder Problems (2020/9/8 追記)この記事を作成したのは2020/04なので,見た目が違ったりバーチャルコンテストの情報が古かったりします. (2020/11/2 追記)少し内容を整理しました. AtCoder Problemsとは, @kenkooooさんが作成したサイトです. AtCoder公式サイトの便利リンク集にも載っています. このサイトでは過去のAtCoderコンテストの問題を一覧することや, バーチャルコンテストに参加することができます. kenkooooさんによるAtCoder Problemsの機能紹介などは AtCoder Problems を支える技術 (2019年版) - 宇宙ツイッタラーXの憂鬱 でされています. また, AtCoder Problemsの右上のLinksからFAQに飛べるので, わからないことがあってこの記事を見た人は先
問題 atcoder.jp 方針 放送局の電波の強さを焼きなましで求める 使用する放送局を頂点とした最小全域木を求める 電波の強さを焼きなましで求める 各放送局の電波の強さを焼きなましで求めました。遷移としてはランダムな放送局を 1つ選んで電波の強さを変化させます。出力強度 は 0 から 5000 までの値をとれますが無駄な変化を避けるためにあらかじめ「このぐらいの強さならこの領域をカバーできる」という情報を計算しておいて、カバー領域が変わらない部分についてはまとめるようにしています。 この計算をしておくことで、電波の強さを変化させたときに「カバー領域が変化しない」ということを避けることが出来ます(この場合は変化のパターンは 0, 250, 450, 700 の 4パターンに限定する)。また、50% の確率でその放送局の出力強度を 0 にします。まとめると以下の通りになります。 50% の
モノグサプログラミングコンテスト(AtCoder Heuristic Contest 009)お疲れ様でした。7,547,834,181点で1位です。ratedコンテストで1位を取ったのは初めてなのでとても嬉しいです。 いつものように解説記事を書きます。 ビジュアライザ (seed=0) 問題概要 前提知識 方針 解説 初期解の生成 焼きなましによる改善 考えたこと・やったこと BFSを書く(~0h41m) 01BFSを書く(~0h50m) スコア計算を実装(~1h15m) 焼きなましを書く(~1h36m) コピー近傍を追加(~2h00m) 初期解の時点でダブらせる(~2h26m) 初期解で乱択ダイクストラ(~2h43m) 高速化(~3h08m) 仕上げ(~4h00m) 感想 問題概要 忘れっぽい高橋くんをできるだけ高確率で出社させてね。 atcoder.jp 説明のため、以下の語句・文字
やったこと ボンドさんの真似 Codingameのローカル対戦環境をdockerでポンする - 接着剤の精進日記 jiro:~/work$ git clone https://github.com/EmulsionBondo/CodingameLocalBattle.git jiro:~/work$ git clone git@github.com:CodinGame/SpringChallenge2023.git jiro:~/work$ curl -OL https://github.com/dreignier/cg-brutaltester/releases/download/1.0.0/cg-brutaltester-1.0.0.jar jiro:~/work$ ls CodingameLocalBattle SpringChallenge2023 cg-brutaltester-
AtCoder Rating History(1) AtCoder Rating History(2) AtCoder ChartsAtCoder ScoresAtCoder Problems(1)AtCoder Problems(2) テンプレネタですね。 各回のコンテストについては別途記事にしていますが、レーティングがキリの良いところを迎えたこのタイミングで、1度総括的な記事を書いておきます。解いた問題数や、コンテスト成績の推移については上の画像参照で。 AtCoderを始める (2019/04) まで 数学 平均的な競プロ上級者と比べても、数学を強みに出来る寄りだと思います。 大学受験数学は全て(ほぼ全て、かも)できる。大学数学科学部レベルの数学は大体理解している。IMO(国際数学オリンピック)が7~8割くらい?解ける(金メダルボーダーくらい)。 ※ 競プロとの親和性が高そうな、組み
この問題集について この問題集は、競技プログラミングの鉄則(E869120 が執筆)に対応した自動採点システムです。 全部で 150 問以上のプログラミング問題が収録されています。 なお、各問題の難易度については、本をご覧ください(前半の章でも難しい問題があります)。 諸注意 問題番号は、原則として扱うトピックごとに割り振られています。 たとえば問題 A01 と B01 は同じトピック(1.1 節)に対応します。 そのため、一部の問題 ID が欠番になっていることに注意してください。たとえば問題 B05(本の 1.5 節に対応)は存在しません。 テストケースについて(10/11 更新) 演習問題のテストケースが公開されました。(リンク) 一部の問題はまだテストケースが入手できていませんが、9 割以上の問題のテストケースが公開されていますので、ぜひご活用ください。 目次 1 章:アルゴリズム
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く