Help us understand the problem. What is going on with this article? このエントリはCompetitive Programming (1) Advent Calendar 2019 4日目のエントリで、バーチャル幼女プログラマーきりみんちゃんが書いています。 きりみんちゃんはVTuberとしてAtCoderの過去問を解く配信をしたりしています。 競プロ、しっていますか？ さて、みなさんは競技プログラミング/プログラミングコンテストというものをご存知でしょうか。 かなり昔から行われているものではあるので、存在は知っているという方が多いかもしれません。 競技プログラミングをざっくり説明すると、期待される入力と出力が定義された問題が出題され、それをコーディングによって解き用意された自動テストを通すまでの速度などを競うコンテストです
AtCoder の言語アップデート で、C++17 対応コンパイラが使えるようになりました。やったー！ この記事では、競技プログラミングに役立つ C++17 の新しい標準ライブラリ・言語機能を 16 個紹介します。 サンプルコードは、AtCoder の GCC 9.2.1 システムで動作を確認しています。 C++17 標準ライブラリ機能 1. 値を範囲内に収める std::clamp(x, min, max) 値 x を、min 以上、max 以下に収めてくれる関数です。 これまで std::max(std::min(x, max), min) と書いてたのが 1 つの関数で済みます。 #include <bits/stdc++.h> int main() { // 値を 0 以上 100 以下に収める std::cout << std::clamp(50, 0, 100) << '\n'
競技プログラミングの問題を自動で解きたい - うさぎ小屋
TL;DR 問い「競技プログラミングの問題は自動で解けるか？」 答え「ある程度は自動で解けるだろう。ただし問題の形式化を人間に任せる必要はある」 問い’「競技プログラミングの問題を自動で解くソルバは、具体的にはどのような形になるか？」 答え’「少なくとも初期のソルバは、最適化付きのトランスパイラと呼ばれるものになるだろう」 このような議論に従い、競技プログラミングの問題の実用的なソルバとして、Python から C++ への最適化付きトランスパイラを開発している。 目次 TL;DR 目次 競技プログラミングの問題を解くとはどういうことか 競技プログラミングのソルバは形式化を人間に任せることになるだろう 競技プログラミングの問題を自動で解くことは不可能ではない 具体例 1 具体例 2 競技プログラミングのソルバは (初めは) トランスパイラの形がよいだろう 競技プログラミングのソルバは (近
興味深いサイエンスニュースをお伝えする「理系通信」。 今回のテーマは「競技プログラミング」です。 「競技プログラミングなんて自分には関係ない」と思うことなかれ。 実は競技プログラミングは、「プログラミングに興味はあるけどやる気が出ない」というような人に最適だというんです。 そんな競技プログラミングのコンテストに、プログラミングのド素人・橋本ディレクターが挑戦。 果たして初心者でも本当に戦えるのか、一体どんな問題が出るのか、そしてなぜ多くの人が熱中するのか。 知られざる競技プログラミングの世界を詳しくお伝えします。 ＃AtCoder＃高橋直大＃chokudai＃競技プログラミング＃プログラミング＃アルゴリズム＃鹿島建設＃競プロ#アットコーダー ◆「ワールドビジネスサテライト」「ガイアの夜明け」などが見放題！ 「テレビ東京ビジネスオンデマンド」はコチラ↓（入会月無料） https://tx
データ分析と機械学習の国際的なコンペティションプラットフォーム「Kaggle（カグル）」のシミュレーションコンテスト「Halite by Two Sigma」で、株式会社バンダイナムコ研究所の技術開発本部のAI（人工知能）研究開発エンジニア會田 翔がGold メダルを受賞しました。 Kaggleでは、オンライン上で企業や政府機関などによるさまざまな課題のコンペティションが開催されており、世界中のデータサイエンティストが参加し、データ分析や機械学習などを用いて課題に挑んでいます。 Haliteは、Two Sigmaが制作したAIプログラミングチャレンジで、複数の船を製造・操作して「Halite（岩塩）」を採取し持ち帰るという４人同時手番のターン制対戦ゲームです。参加者は、このゲームをプレイするAIを開発し、提出します。Kaggle上では、登録されたAIのうち実力が近い者同士がマッチングされ、
24時間耐久ノンストッププログラミングコンテスト（TCO20 Marathon Final） - TopCoderの学習のお時間
Competitive Programming (1) Advent Calendar 2020 11日目の記事です。 Topcoder Open 2020 について書きます。 tco20.topcoder.com Topcoder Open(TCO) とは Topcoderが年に1度開催している、世界最強プログラマー決定選手権です。 1年ほどかけて予選が行われ、そこで勝ち抜いた各部門*1の10人ほどが、例年11月くらいにアメリカで行われる決勝に招待されます。 TCO20 今年はパンデミックのせいで例に漏れずオンラインでの開催になりました。かなしいね まあプログラミングコンテストなのでオンラインでも十分実施可能… と思いきや、Marathon部門は決勝は例年 10時間コンテスト で、オンライン開催で10時間コンテストやろうとすると時差が困ったねということに。 これは無理みたいな感じ 色々協
AtCoder Heuristic Contest 001 (AHC001) 初心者向け解説 - TERRYのブログ
AtCoder Heuristic Contest 001 (AHC001) の参加記を書くはずだったのですが、記念すべき第1回ということで「マラソンに初めて参加したけど、感想戦TLで周りが何を言っているか分からない……。」という方が多そうな気がして、気付いたら初心者向け解説記事*1を書き始めてしまっていました。 ふぁぼ圧、強すぎませんか https://t.co/DuGViXzI80— TERRY (@terry_u16) 2021年3月15日 参加記はまた後日書きます。→書きました。 www.terry-u16.net 問題概要 はじめに 正の得点を得る（823,090点） 山登り法を導入してみる（452億点） ちょっと改善してみる（469億点） 焼きなまし法を導入してみる（477億点） さらなる改善 Tips 手元でテストケースを回す コンテスト序盤は特に丁寧にコードを書く 愚直判定
Advent Calendar 2020 : プログラミングコンテスト参加中の心拍数を測定してみる - kmjp's blog
この記事は、Competitive Programming (1) Advent Calendar 2020 - Adventarの17日目の記事です。 読んでも競技プログラミングの実力は上がりませんので、ご注意ください。 過去の分はこちらです。 Advent Calendar 2016 : ABC#001のA問題をコンパクトに解く - kmjp's blog Advent Calendar 2017 : CPHBを少しだけ和訳してみた(前編) - kmjp's blog Advent Calendar 2018 : ブログを書く速度を少しだけ上げる - kmjp's blog Advent Calendar 2019 : 高橋君は何問登場したか？～高速に問題をブラウズする - kmjp's blog 目次 目次 はじめに 実験結果 プレッシャーがないとき ◆ABC185とLeetCode
この記事はCodinGameの一人用最適化ゲームの紹介記事です。 CodinGameといえば対戦ゲームが定番ですが、一人でやる最適化ゲームも実はけっこう充実しています。このたび全ての最適化ゲームをプレイし終えたので、それらの紹介記事を書いてみることにしました。 Optimizationカテゴリ CodinGameにはOptimizationというカテゴリがあり、最適化ゲームはそこに分類されています。このカテゴリのゲームは一人でプレイし、ハイスコアを競います。 Optimization ゲーム一覧 この記事で使う指標 ・公式評価 CodinGameユーザーによる投票の５段階評価の平均点（2021年3月14日 現在） ・私の評価 私が好きかどうか ★１～★５（好きでない～好き）の５段階で評価 ・問題の単純さ 問題の内容が分かりやすいか ★１～★５（分かりにくい～分かりやすい）の５段階で評価 ・
何も分からん、になった回でした。 問題 問題文(原文)はこちら 要約すると、 N*Nのグリッドと、D人のダンサーの位置が与えられる。 ダンサーは1ステップごとに上下左右に隣り合うマスに移動することができる（移動せずにそのマスに留まってもよい）。また、ダンサー1人ごとに、あるステップ数目の終了時点で居なければならない位置が入力として与えられる。 グリッドの各マスにはC色のうちどれかの色がついており、ダンサーが別のマスに移動すると、移動先のマスの色が別の色に変化する（移動しなかった場合は変化しない。また、複数人が同時に同じマスに移動した場合は、移動した人数と同じ回数だけ変化する）。どの色からどの色に変わるかはマスごとに入力として与えられる。 Sステップ終了後、(ある1色の連結成分の数)2の、全色についての総和が小さいほど良いスコアとなる。 という感じです。 やったこと 最後に提出したコードはこ
こんにちは、ganariyaです＞＜ 主に競技プログラミングを嗜んでいます。 先日、改善型コンテスト（マラソン）がAtCoderに定期開催されるとのことで、その導入コンテストとして「Introduction to Heuristics Contest」が開催されました。 今回は、その参加記ならびに焼きなましに対する自分の理解やマラソンでの個人的な方針をまとめようと思います。 ganariya 問題ページ 自分の提出 公式解説 コンテスト中の方針 問題を読むと分かりますが、問題B、CをやってからAをやるといいと書いてあります。 僕はマラソン系初心者なので、Bから解き始めました。 Bは、Aでのスコア計算プログラムを書こう！というものでした。 これはそんなに難しくなく、300点ぐらいの内容でした。 公式解説はRustのため、C++で書く場合はどうなるか載せておきます。 LL get_score(
TopCoder Marathon Match 120 "ReversalSort" - iwashi31’s diary
問題概要 長さ N の数列が与えられる。下記の操作を任意回行って、コストをできるだけ抑えつつ昇順ソートせよ。 数列中の連続する区間を好きに選んで、その区間内の数列を反転する。コストは floor((区間の長さ)X)（X は入力で与えられ、0.0 ≦ X ≦ 3.0）。 全文はこちら。 解法 以下の 4 つの解法を試して、一番良かったものを採用する。 アルゴリズム概要 有効な X ① バブルソート 2.2 ~ ② 選択ソートっぽいやつ ~ 0.1 ③ 選択ソートっぽいやつ改 1.8 ~ 2.3 ④ 隣り合う要素の差の合計を最小化する貪欲 0.1 ~ 1.8 ① バブルソート X が大きい場合、バブルソートが最適解になる。 最適解になるのは X ≧ 2.71 くらいからのはずだが、他のアルゴリズムがかしこくないせいか X = 2.2 くらいでこれが採用されることもあった。 1 1 1 0 3
CODINGAME SPRING CHALLENGE 2020で初Silverを獲りました。 - matsu7874のブログ
"CodinGame Spring Challenge 2020"に参加しました。 CodinGameにはリーグという階級分けの制度があり、各リーグのBOSSを基準にWood2, Wood1, Bronze, Silver, Gold, Legendと登っていきます。今回のコンテストで初めてSilver(の上位)まで到達することができました。 作成したAIも自分より強い敵にぶつかりに行ったり、同じ場所を往復したりはしない状態になりました。 Gloval rank 702/4976、Silver rank 57/999と満足のいく結果となった。 参加経験 CodinGameへの参加は2018年のXMAS RUSH, 2019年のUNLEASH THE GEEKに続いて３度目の参加で、今回のコンテストで初めてSilver Leagueへの進出を果たしました。 これまでに参加したコンテスト 取り
3月19日に第9回 SamurAI Coding の決勝戦が行われた。私はチーム Monk1 の一員として参加させてもらった。期間が (他のコンテストと比較すると) 長めだったこともあり、すべて終わった今としては多少の悔しさと軽い達成感がある。せっかくなので、記憶が薄れないうちに参加記として残しておこうと思う。 なお、チームメイトの montplusa くんによる参加記もあるので是非どうぞ。私のこれはタイトルの通り日記なのであまりおもしろいものでもないと思う。彼の参加記は AI そのものや戦略の話に重点を置いているので有益だと思う。 montplusa.hatenablog.com そもそも戦略については多少のアイデアを加えたのみでほとんど彼に任せっきりだったので、なんと決勝ラウンドに提出された AI の仕様変更を完全には把握していない。でもこれは日記なのでそれはいい。私の視点から見た各時
第5回 Asprova Programming Contest 参加記 - 特異点の向こう
競プロの記事を書くのはこれが初めて。興味のない人は読み飛ばしてください。 12/30から1/6にかけてAtCoderで行われた、第5回Asprova Programming Contestに参加した。マラソンマッチに参加するのは初めてなのでいろいろ勉強になったことやコンテストの感想を書く。 コンテストについて 工場の生産スケジューラーを開発しているAsprovaが主催するマラソン型のコンテスト。第5回の問題は、とても簡単に言うと「ある工場において、注文の数量や納期、機械（主資源）の性能や従業員（副資源）の仕事の有無などのデータが与えられ、それぞれの注文に適切な資源を割り当てて利益を最大化するスケジュールを組め」というもの。一週間の間に、もっとも効率的な解を求めるプログラムを書く。 年末年始に行われる異常なコンテストだったが、参加者は50人以上いてびっくりした。第4回は80人くらいいたらしい
intro-heuristics AtCoder Contest Scheduling - ほげ - omi
https://atcoder.jp/contests/intro-heuristics/standings 20 位。ギリギリ1ページ目に乗った ~21:00 テンプレートの準備。 rdtsc と焼きなましテンプレはコピペして、ONLINE_JUDGE があるので input() の受け取りをするかどうかを環境で切り分ける部分も先に書いておいた。 cat /proc/cpuinfo で CPU が 3.00 GHz に上がっていることを確認して rdtsc の定数をちょっと書き換えたりした。 21:00~ 21:09 A を読んでから B を解く。 やりたいことはなんとなくわかったけど、サンプルが D=5 なせいでちょっと手間取る。こういうのは const int D=365; したくなる人間なので……。 なんとか直して提出！ なんで？ 毎行出力させるのを忘れていました。ちゃちゃっと直し
CodinGame Spring Challenge 2020 に参加した - saika_toto’s diary
ツイッターで何度か流れてきたので途中から試しに参加してみたらめちゃくちゃ熱を上げてしまった。わりとしっかりしたメモを残していたうえ、思いがけずかなり気持ちになってしまったので感想を書いておくことにする。 まずコドゲに登録した日が1週間くらい前になるらしい。正直に言うと最初にルールを読むだけで疲れてコードを初めて書いたのは何日か経ってからだった。 13日にコードをいじり始めたが、そもそもAtCoderしかしたことがないので初期コードを読むだけで一苦労だった。とりあえずwoodでは使わないとコメントされているスキル周りの受け取りを削った。これで受け取りはできていると思ったので、出力をいじるためにペレットの情報を受け取ったら、スーパーペレットから順に一番近いペレットにそれぞれのパックを向かわせることにした…ところ見事に出力が壊れた。パックをちゃんと指定できていないのかなあと思って色々試しても何も
はじめに CodinGameのコンテスト（CodinGame Spring Challenge 2020）に参加しました 結果は世界61位（LEGEND）、日本12位と健闘出来たかなと思います Legendリーグは114人いて日本人が18人なのでLegendのうち6人に1人くらいが日本人だったみたいですね みんな強い ルール 詳しいルールはツカモさんが記事にしているのでそちらを参照するのが良いと思います 簡単に言うと、パックマンで相手よりたくさんポイント（ペレット）を集めたほうが勝ちで、パックマンのタイプによってじゃんけん要素が加わった感じです tsukammo.hatenablog.com やったこと リーグ別に段階を踏んで改善していったものも書きますが、ここでは最終的にどんなことをやったのかだけ簡単にまとめておきます 基本的には貪欲とルールベースで評価関数によって行動を決定していました
Topcoder 初めてのTopCoderマラソンマッチ。34位/68人とちょうど真ん中の成績でした。 問題概要 のグリッドの各マスが 色のうちいずれかで塗られている。 人のダンサーがいて、 単位時間かけてグリッド上を移動する。このとき各マスが1回踏まれるたびに、周期 で色が変化する。色変化のローテーションはマスごとに異なる。 各ダンサーについて、「ある時刻にこのマスにいなければいけない」という制約条件がいくつか与えられる。同一ダンサーの、時系列で見て隣り合う2つの制約条件を両方満たすことができること（つまり、指定時刻の差が指定マス間のマンハッタン距離以下であること）は保証される。 全てのダンサーの移動が完了したグリッドにおいて、各色それぞれの連結成分の個数を数える。色 の連結成分の個数が であるとき、 がスコアとなる。 スコアが小さくなるようなダンサーの移動経路を出力せよ。 方針 焼きな
下記の日時に開かれた競技プログラミングコンテスト、AtCoder「第4回 RECRUIT 日本橋ハーフマラソン」の備忘録です。 予選：2020/02/15(土) 19:00 ~ 23:00 (240分) 本戦：2020/03/07(土) 14:00 ~ 18:00 (240分) 第四回ハーフマラソン景品 結果 予選：1/525位、本戦：57/76位でした。※有効回答者のみカウント。 予選は生まれて初の優勝 & 初の本戦進出となり、嬉しかったので記念に参加記を書きます。 予選：考えたこと・やったこと 前日の2/14(金)にDevSumiに登壇したため睡眠不足状態でした。睡眠を補給すべくお昼寝を計画。コンテスト中のガソリンとしてチョコレート・クッキー・グミ・オレンジジュースを買い込んだ後、紅茶を飲みカフェインによる90分後の覚醒期待してベッドへ。 仮眠を取る。— ツカモ (@tsukammo)
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
数学得意じゃない系の社会人エンジニアに競プロとAtCoderを全力で布教したい。あるいは競プロのよくある誤解と楽しむコツ - Qiita
競プロに便利な C++17 新機能まとめ - Qiita
未経験者のアナタもハマる？競技プログラミング「AtCoder」って何だ？【理系通信】（2021年3月19日）
バンダイナムコ研究所のAI研究開発エンジニア国際的コンペティションKaggleの「Halite」でGoldメダルを受賞
CodinGame 最適化ゲームの紹介 - ヴァルの開発記
MM118 参加記 - takumi152の競プロ日記
Introduction to Heuristic Contestで焼きなましを学ぶ - Qiita
SamurAI Coding 2020-21 参加日記 - /tmp
接着剤の「CodinGame Spring Challenge 2020」 参加記 - 接着剤の精進日記
TopCoder Marathon Match 118 DanceFloor 参加記 - ARMERIA
第4回 RECRUIT 日本橋ハーフマラソン に参加しました。 - tsukammoの収穫記