ICPC 2021 国内予選参加記

ICPC2021国内予選の問題文を公開しました。通過チームは後日発表します。https://t.co/Id90TiiUJC (順位表)https://t.co/abVmvZe4XU (問題)https://t.co/lO6bLjiVir (English) — ICPC2021JP (@icpcjapan) 2021年11月5日 KyopRo-jinで出場していました。5完20…

手続き型プログラミング基礎レポート

大学の授業で書いたレポートです。 5000頂点程度の三角不等式が成り立つ巡回セールスマン問題を、C89で3sec制限で解くコードを含んでいます(15~60ページ) 引用する際は、 eiya@大学垢 (@eiya5497313) | Twitter に連絡していただければ本名を教えます。

【writeup】nitac_mini_ctf、PPC問題のACコード

Pathway and Street Bの道(コスト101333)を通りたく無い。(が、やむを得ず通らないといけない場合もある) そこで、コストを「firstをBの回数、secondをAの距離」となるpairで持つとそのままダイクストラ出来て良いです。 (段階的に渡れるBの数を増やす…

ICPC2018国内予選参加記(仮原稿)

ICPC2018国内予選参加記(仮原稿) ICPC2018国内予選の参加記です。本当は別の場所にまともなのを書こうと思っていたんですが、どうも時間が無さそうなのでここで雑に書いてしまいます。 60°(sixty_deg)さん、baton(goodbaton)さんとeiyaで60odnightとして参…

AtCoder Regular Contest 098参加記

部内での共有用に久々に書いてみようと思います。 まあ参加記であって解説では無いんですが...AtCoder Regular Contest 098 - AtCoder C - Attention リーダーを決めると、後は他の人がどちらを向いているか数えるだけになって嬉しいです。 が、よく見るとN …

SoundHound Inc. Programming Contest 2018 (春):D - 建物 を解いたという日記

問題:D - 建物 ・DP(H,W)っぽい ・bitDPをしたいけど、制約的に不可能 ・「部屋 (1,j) からスタートして(H,任意)から建物を出るときの最大利益」と誤読 ・入室回数を出来るだけ減らしたいので、通過or往復で、解説の図のような通行しかしない <=解説の図 ・…

2buttonsのeiya解

https://hoj.hamako-ths.ed.jp/onlinejudge/contest/121/problems/5 提出しても見られないみたいなのではるだけはっておきます。ところで通常問題の方のURLをはりたかったのですが、なんかidがずれるみたいなのではりません。 現時点(2017/12/2)ではidは86…

F - Three Gluttons(CODE FESTIVAL 2017 qual C)

この問題です。 F - Three Gluttons1800点問題自力AC!!!!!!!!!!!!!!しかも所要時間は別の問題の考察してる時間も含めて2時間半!https://t.co/HMyqIqeNNM— eiya@受験競プロC++@DDCC (@eiya5498513) 2017年10月22日 というわけで解説と考察の道…

旧AtCoderからbetaAtCoderに移るスクリプト(未完)

旧AtCoderからbetaAtCoderに移るtampermonkey用スクリプトです。 上の方に変なのが見えるようになります。 使えればよし精神を大事にしていこうな(逃げ) 僕にはこれが限界なので、もっと良いのを誰か作って。追記>Luzhiledさんが作ってくれた。ありがとう…

最古の遺跡解説

この問題です ジャッジ:C - 最古の遺跡 問題:https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf オーダー的にO(N3)が辛くてO(N2)が通るので、O(N2)を考えます。 二点を固定して、残りの二頂点C,Dに点があるかを判定すれば良いです。 まず…

tupleを展開して関数に渡す関数

tupleを展開して関数に渡す関数 boostを使えば出来るらしいけど、知らない。 出来栄えはかなり雑です。 template <class F, class... Ts, class... Us> typename std::enable_if< sizeof...(Us) == sizeof...(Ts), std::result_of_t<F(Ts...)>>::type apply_impl(F&& fun, std::tuple<Ts...>&, Us&... us) { retur</ts...></f(ts...)></class>…

プリム法の証明

かなり乱暴なことをしている気がします。厳密な証明は他をあたってください。 プリム法とは 最小全域木を構成するアルゴリズムの一つです。 以下の手順で行います。 ある頂点を選び、木Tに追加します 木Tから最も近い頂点を木Tに追加します Tが全域木になる…

O(ElogV)ダイクストラのテンプレ

O(ElogV)ダイクストラのテンプレ #include <queue> #include <vector> #include <functional> #include <utility> #include <algorithm> #include <iterator> using COST_T = uint32_t; constexpr uint32_t N_MAX = 変える; constexpr COST_T INF = 変える;//std::numeric_limits<double>::infinity() #if defined(_MSC_VER) &&</double></iterator></algorithm></utility></functional></vector></queue>…

N次元配列を同じ値で埋めるテンプレ2

N次元配列を同じ値で埋めるテンプレ キャストが要らないバージョン シンプルなのはこっち:N次元配列を同じ値で埋めるテンプレ - 永夜の記録 #include <type_traits> template<typename T, typename U> typename std::enable_if<std::rank<T>::value == 0>::type fill_all(T& arr, const U& v) { arr = v; } tem</std::rank<t></typename></type_traits>…

C++14用mod_int

C++14用mod_intです。勝手にmodを取ります。 型名はmintです。 using mint = mint_base<1000000007>; の1000000007がとるmodになります。 +-*/やインクリメント,デクリメントが出来ます。 ~で逆元を取れますが、そのままでも割り算が使えます。(どちらもlog…

N次元配列を同じ値で埋めるテンプレ

N次元配列を同じ値で埋めるテンプレを置いておきます template<typename T> void fill_all(T& arr, const T& v) { arr = v; } template<typename ARR, typename U> void fill_all(ARR& arr, const U& v) { for (auto& i : arr) { fill_all(i, v); } } 使用例 int dp[1000][1000]; fill_all(dp,-1);/</typename></typename>…

JOI2012予選4「暑い日々」のオーバーキル考察

JOI 2012-2013 予選 問題4 これの解答に触れられているものの解説されていない想定オーバーキル考察です。

幅優先探索の一般的な罠

幅優先探索でTLEする一般的な罠の解説です。 こういうグリッドを幅優先する問題で起こりやすいですね。 C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder 簡単のためこのような迷路を考えます。(#壁、.通行可) /abcdef 1###### 2####G# 3###..# 4##…

セグ木テンプレ

C++11用オレオレセグ木テンプレです。 「変更するコードここから」の下を書き換えて使います。 segment_tree<int, 1000> seg; で要素int,大きさ1000のセグ木が出来ます。2の累乗には勝手に拡張するので1024でなくて良いです。 これをそのまま使うのではなく、これは一例</int,>…

情報オリンピック布教用チラシ

学校でプログラミング講習なるものをやっていたので、先生に言って受講生に配らせてもらったチラシです。なので、プログラムが少し書けることを前提に累積和を入れてあります。 デザイン能力が無いのでみんなで改善してね(?) (配布の際は1,2ページを表面…

JOI布教用チラシ(図抜け)

【追記】ちゃんとしたやつをここにあげたのでそっちを見てね。 eiya5498513.hatenablog.jp 以下元記事...

ABC058/ARC071 D問題解説

D - 井井井 / ### 問題のURLはこちらです。 D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder

AGC011 A Airport Bus:実装の解説

A: Airport Bus - AtCoder Grand Contest 011 | AtCoder 解法:早く着いた人からバスに乗せていけば良いです。 以下、実装のテク。 バスには必ず一人以上乗っている。そのバスの出発時刻は保存しておく。 とします。 始めに、1番目の人をバスに乗せます(ま…

SRM 245 Div2 Med (Problem 600) Flush:日本語訳のようなもの

フラッシュ eiya君はフラッシュというカードゲームをしています。このゲームは、手札の中の同じマークのカードの枚数の最大値が得点になります。例えば、手札にスペード5枚、ハート2枚、他0枚の場合、5点です。eiya君はこのゲームを有利に進めたいです。 eiy…

topcoderのstd::bad_alloc

topcoderでstd::bad_allocが投げられて、自分のコードのどこからもstd::bad_allocが投げられていないとき、それはtopcoder側の採点の際のCLASSのnewで投げられているかもしれない。 classの中に大きな配列を置くのはやめましょう。グローバルにしましょう。 …

(書きかけ)TopCoderの設定記録(Windows)

主に自分用。(書きかけなのに公開するなという話もある) WindowsでTopCoder環境を整える。 面倒な人へ 完成品が僕のgithub上にあげてあります。 topcoderアカウントの取得とjavaのインストールをした後、!TopCoder起動から立ち上げて、 Options->Editor->C…

MujinProgrammingChallenge2017A問題:eiya解

MUJIN2017のA問題の僕の解法です。問題はこれ:A: Robot Racing - Mujin Programming Challenge 2017 | AtCoder 考察 1番目のやつよりも2番目のやつの方が先にゴールするには、1番目のやつを2番目のやつが跨ぐ必要がある。同様に、i

JOI2017本選落ち

成績は118点(1+2部分点)でした 少なくとも部分点取れる方針は出てたはずなのにほぼ取れてない。 緊張もしてなかったはずなので完全に実装力の無さが露見していて人権が無い。 — eiya@受験待機組 (@eiya5498513) 2017年2月12日 誤読 pic.twitter.com/cKwfgp…