programming contest
Google主催の競技プログラミングコンテストであるGoogle Code Jamがついに2023年にcloseしてしまいます。 https://codingcompetitions.withgoogle.com/codejam/faq によると、2023-06-01でサインインが不可になり、2023-07-01にはサイト自体がシャットダウン…
競技プログラミングで使いたいと思いつつずっと未履修だったbitsetの使い方を勉強しました。 基本操作 以下ではすべて以下が書かれているものとします。 #include <bitset> #include <iostream> using namespace std; 初期化は、文字列を与えるか、整数を与えるかで行えます。 </iostream></bitset>…
AtCoderやCodeforcesなどの競技プログラミングサイトでは、通常、標準入力から入力を受け取ります。例えばPythonで回答する場合、あなたの回答(例としてsolve.pyとします)は、入力が書かれたテキストファイルinput.txtが $ python solve.py < input.txt の…
競技プログラミングでC++を使うときに、入出力を高速化する目的でおまじないのように書かれる ios_base::sync_with_stdio(false); cin.tie(0); の意味、実はよくわかっていなかったので c++ - Significance of ios_base::sync_with_stdio(false); cin.tie(NU…
Google Code Jam 2020 Round 1Cの最終問題であるOversized Pancake Choppersの解説です。 この問題はTest Set1から3の3つから構成されます。本番ではTest Set 1のみ解けました。この記事ではTest Set2とTest Set3について解説します。 問題概要 N個のパンケ…
約1年ぶりにCodeforcesに出場しました。Div. 2の4問目、Orac and Medians が解けそうで解けませんでした。終了後、解説を読みながら考えをまとめました。 問題概要 数列が与えられる。この数列の任意区間を選び、その区間のすべての値を、その区間の中央値で…
Google Kickstart 2020 Round 1Bの最後の問題、Wandering Robot についてやっと理解できたので解説を書きます。 問題概要 W*Hの盤面が与えられる。盤面には ある矩形1つ分の穴が空いている。ロボットは左上の(1, 1)を出発し、等確率で右か下に移動する。た…
競技プログラミングでC++のmultisetをたまに使うことがありますが、毎回使い方を忘れているのでメモしておきます。 (2021-09-05追記: 計算量に誤りがあったので修正) multisetとは multisetは、集合を扱うデータ構造です。setと異なり、同じ値の要素を複数持…
Windows 10にTopCoderのための環境を構築したときの簡易的なメモです。 Javaランタイムのインストール Java SE Runtime Environment 8 - Downloads からJavaのランタイムを入れる chocolateyを入れている場合、choco install jre8 でもいいはず Java Applet…
HACK TO THE FUTURE 2019予選に参加しました。8時間中7時間半ほど参加して22位でした。前回より1位だけランクアップしましたが順位表の1ページ目には入れず残念。 試行ログ まずは周囲に壁をつくるだけの初期配置を試し、80904点。 マークを盤面いっぱいにラ…
本番中にパニクって解けなかったのを反省して解き直しました。DFSくらいさっと書けないとだめですね…。 問題 C - 七目 9x9のマスが白で埋められている。白マスが縦・横・斜めのいずれにも白マスが7個以上連続しないように、11個のマスを黒く塗る塗り方を求め…
2018-09-19のTopcoderに3ヶ月ぶりで出場。実験を執念で繰り返してかろうじてEasyが解けました。あわててNimゲームの勝利条件を蟻本で確認しましたが、もはやこれが前提知識となっているとは。 以下、Easyの解法とPythonコードです。 #!/usr/bin/env python3…
2018-09-15のAGCに出場。Aと、Bの部分点が解けて325位。Bは考え方は正しかったのですが、計算途中のオーバーフローに泣きました。上位陣でもBはスルーしている人が多かった中で、DPをやりたくなる衝動を抑えつつ部分点が取れたので、少し自信が付きました。…
全然分かりませんでしたが、解説を見て理解できました。思いつけば簡単な問題なので悔しいです。 問題:D: All Your Paths are Different Lengths - AtCoder Regular Contest 102 | AtCoder 問題概要:パスの長さが0..L-1のちょうどL通りになるグラフを生成 …
問題:B - Neutralize 問題概要:N個の薬品が並んでいる。各薬品の効用は-109 ~ 109。連続したK個の薬品の効用を0にする処理を任意回おこなったあとの薬品の効用の和の最大値を求める。 400点問題なのに2時間考えてまったくわかりませんでした。実行時間制限…
おとといのAGCに参加して1問しか解けず。Bに二時間以上考えて解ききれないというのはさすがに問題だと思い、解説を読み込んで自分なりに咀嚼しました。本番で書いていたひどすぎるコードが消えてすっきりしました。しかし、本当に思考に穴がないかはまだ自信…
Div.2に落とされた直後のSRMで、自己最高の4位を取ることができました。本当は同時開催のTCOに出るつもりだったところ操作ミスでSRMにエントリーしてしまっていたのですが、結果オーライでした。記念のスクリーンショット。 本番では解けなかった1000のMajor…
TopCoderのプラグインGreed(詳細はTopCoder の強欲プラグイン、Greed を使う!)で自動生成したコードをVisual Studioでビルドすると以下のようなエラーが出ます。 error C2872: 'data': あいまいなシンボルです。 note: 'std::ifstream data' である可能性…
先週の大会に引き続きHACK TO THE FUTURE 2018予選 - HACK TO THE FUTURE 2018予選 | AtCoderにも参加しました。8時間フルで参加して23位でした。 思考ログ まずは以下のようなgreedyに山を作る方法を試しました。 盤面Aと盤面Bとでもっとも差分が大きいマス…
第2回 RCO日本橋ハーフマラソン 予選 - 第2回 RCO日本橋ハーフマラソン 予選 | AtCoder に参加しました。結果は16位で、青コーダーの自分にしては健闘。去年の本戦のパラレル | AtCoderでも2位という今後二度と取れそうもない順位が取れてしまっていたので、…
1stに引き続きHokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017に参加しました。1stより十分な時間をとって臨んだおかげで、最終提出時18位、最終テスト後19位。目標としていた上位25%に滑り込めました。 考え方 序盤は迷走しましたが、中盤…
前回に引き続き、Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017 の参加記を勝手ながらまとめました。見つけ次第追記します。 順位 atcoderのID URL 1 yosss AtCoder 北大日立マラソン 2nd 参加記 (yosss), twitter 2 yowa AtCoder 北大日…
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 - Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 | AtCoder に参加していました。自分はほとんど何をやっていいかわからず191位 / 297位でした。 参加してから他の方の…
Pythonのitertoolsモジュールには、イテレーションに関する便利関数が多数用意されています。この記事では、その中でも競技プログラミングで全列挙に使える関数についてまとめます。Python 2.x, 3.xのどちらでも使えます。 Google Code JamのSmallでは全列挙…
先日久しぶりに参加したCodeforces Round #368 (Div. 2) - Codeforcesの C. Pythagorean Triples が面白かったのでご紹介します。 問題 「正の整数aが与えられる。三平方の定理 a2 + b2 = c2 を満たす残りの 正の整数b, cの組を一組答えよ。そのようなb, cの…
ワーシャルフロイド法というのを使うと、グラフのすべての2頂点間の最短路を求められるらしい。蟻本を参考にして解いてみた。以下のグラフを例にとって、全点対の最短路を求める。 コードは以下。 #include <cstdio> #include <algorithm> #define REP(i,n) for(int i = 0; i < </algorithm></cstdio>…
異なるn個のものから、重複を許してr個を取り出して列をつくることを、n個からr個とる重複順列という。これをC++で全列挙することを考える。例題として、1〜5の数字を使ってできる3桁の数字を全列挙することを考える。そのコードは以下の通り。 #include <iostream> #i</iostream>…