競技プログラミング

ABC147 E Balanced Pathでbitset高速化を完全に理解する

本番で通せなかったABC147のE問題『Balanced Path』について、反省していきたいと思います。 問題概要 H*Wのグリッドの各マスに数が2つ書かれている。グリッド上を(0,0)->(H,W)にy+1orx+1で移動するとき、経路上の各マスについて、いずれかを選び、「その合…

なぜ"Colorful Hats 2"に35分も掛けてしまったのか。

Colorful Hats 2は三井住友信託銀行プログラミングコンテスト2019のE問題です。本番ではこの問題に35分かかったので、振り返りをします。 三井住友信託銀行はどこに競技プログラマ需要があるのでしょうか?気になりますね。 問題概要 a = [A[0:i-1].count(A[…

HACK TO THE FUTURE 2020予選の参加記

2019/11/02に行われたHACK TO THE FUTURE 2020予選に参加しました。 解法はダイクストラ(曲がり回数100ゴールからの距離を負のコスト+4近傍のブロックの個数の2乗-ゴールからのマンハッタン-5)からの不要矢印削除で、最終成績は07:32に提出した4,941,365点…

コンテストの開き方(ゆるふわ競技プログラミングオンサイト編)

ゆるふわ競技プログラミングオンサイトについて、コンテスト準備の流れを書こうと思います。主にHackerRankでの開催を念頭においています。今後、有志コンテストを開く方の参考になれば幸いです。

Rimeの使い方 誤答の区別とHackerRank用の出力方法について

この記事では作問補助ツールRimeの使い方のうち、誤答の種類を区別する方法とHackerRank用のzipファイルの作り方を解説します。 その他の情報が欲しい方は、下記の記事と公式ドキュメントを読みましょう。ほとんどのことが書かれています。 Rimeの使い方 - b…

私が競プロerと働きたい理由

競プロerとは この記事で「競プロer」といえば、AtCoderとかCodeforcesとかのような、1~2時間で4~6問題に取り組む形式のコンテストに頻繁に参加しているプログラマのこととします。 競技プログラミングには、ゲームAI(CodingGame)とか最適化(TopcoderのMM)の…

『ナルハヤのつるぎ』を競技プログラマーが遊ぶ

『ナルハヤのつるぎ』という面白いゲームを手に入れたので、競技プログラミングの問題風にして遊んでみたいと思います。 『ナルハヤのつるぎ』とは? 6枚のカードを組み合わせてお題の剣を揃えるスピード系パズルゲーム。 【GM2019春】ナルハヤのつるぎ 紹介…

0-1ナップサック問題入門(if文とfor文と配列を前提とする)

この記事ではナップサック問題を解くプログラムをPythonで実装します。 再帰関数も動的計画法も使わず、if文とfor文と配列を使って解くことを目指します。 ナップサック問題とは ナップサック問題とは次のような問題です。 いくつかのアイテムと1つのナップ…

ゆるふわ競技プログラミングオンサイト@FORCIAを開催しました

ゆるふわ競技プログラミングオンサイト @FORCIAという競技プログラミングの有志オンサイトイベントを開催したので、企画者目線で振り返りを書きます。

2次元の凸包を求めるアルゴリズムと応用について

2次元の凸包(convex hull)を求めるアルゴリズムについてまとめました。また、凸包の応用先を列挙し、凸包を使って解ける競プロ問題を集めました。ギフト包装法(Gift wrapping algorithm),QuickHull,グラハムスキャン(Graham's scan),Monotone Chain,Chan's a…

Competitive Programming Advent Calendar 2015, 2016まとめ

Competitive Programming Advent Calendar 2015, 2016を中心に、言及されている記事を集めました。 私が特に「いいね」と思ったものについては★を付けています。

もっと気持よくyukicoderで遊ぶためにテストケースを自動実行する。

solorab.net このブログを読んだんですが、謎の呪文が1行だけ貼ってあって????ってなりました。 テストケースは自動で確かめる ちょうどTwitterでも強い人はテストケースを自動実行しているようだということを見ていたので、自分もオシャレに自動でテス…

素数は通れませんの裏話

Advent Calendar Contest Advent Calendar(以下ACCAC) 2015でNo.308 素数は通れません - yukicoderを出題させていただきました。 www.adventar.org 自分はyukicoderの★3を解くのにヒーヒー言う僕が、ACCACの初日に★4の問題を作れてしまったので、 作るときに…

ABC#027の感想

すっかり存在を忘れていて残り時間30分からの挑戦。 Cの解法は解説読んでも釈然としません。 http://abc027.contest.atcoder.jp/ A: 長方形 - AtCoder Beginner Contest 027 | AtCoder a,b,c = [int(x) for x in input().split()] if b==c: print(a) elif c=…