チーム Royal Blue としてICPC2021国内予選に参加しました。 私としては5度目の参加で最後のICPC大会になります。 チームメイト NOSS: 自分 mhrb: チームとして組むのは3度目。一番チーム歴が長い。 Rogi: 確かICPC初参加だけど、部内予選1位。いつのまにか…
NOSS, まほろば, まつしたの3人で横浜国立大学チームChabashiraとしてICPC2020アジア地区横浜大会に参加しました。 2019地区大会参加記 2020国内予選参加記 1日目 受付・開会式 zoomでカメラ越しに学生証を提示して本人確認をしました。 実は、ずっとオンラ…
問題 問題リンク：https://codeforces.com/contest/1473/problem/F 次を満たす集合 を'strange'とする。 'strange'である集合 に対し の最大値を求めよ。 解法 いわゆる、「燃やす埋める問題」に落とし込めるので最小カットで解くことができる。 正負のペナ…
問題 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403 解法 頂点に重み付きの価値がついているグラフの最大独立集合を求める問題。 なので枝刈り探索によって解くことができる。具体的な枝刈り方法はwataさんのスライドのp.28以…
チーム Chabashira (NOSS, まほろば, まつした)としてICPC国内予選に参加しました。 追記(2020/11/09) チームメイトの参加記 - ICPC2020国内予選参加記 - まほろば精進日誌 - ICPC2020国内予選に出場しました｜MacaronBLOG 開始前 開始直前まで研究室のタス…
問題 文字列Sを部分列に含む回文であって長さが最小であるもののうち、辞書順でk番目のものを求めよ。 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362 解法 まずは最小長さを求め、最小長さとなるような回文の個数を数え上げる…
問題 bitからなる異なる 個のbit列が与えられる。1回の質問でbitを1つ明らかにできるとき最悪でも何回の質問でbit列を1つに特定できるか求めよ。 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302 解法 まず前計算として、 cnt[S…
問題 8点の座標が与えられるので(x,y,z)を自由に並びかえたとき立方体の頂点できるか判定せよ。 問題リンク：http://codeforces.com/problemset/problem/465/D 解法 各点の座標の並べ方は 通り。1点固定して他を全探索しても高々 通りなので全探索できる。 …
問題 JOI 2010 本戦の問題 問題リンク：AOJ 0552 解法 かなり難しかった。 そのままの座標だとマンハッタン距離が扱いずらいので45度回転をする。すると、例えばと変換すれば距離はで求められるようになる。点群の最遠点対の距離はで求まり、s,tで分離して考…
チームEldoradoとしてICPC 2019 Asia Yokohama Regionalに参加しました。 チームメンバーの参加記 ICPC 2019 Asia Yokohama Regional参加記 - むだにくろうす ICPC 2019 Asia Yokohama Regional 参加記 - まほろば精進日誌 一日目 開場です pic.twitter.com/…
ハル研プロコン2019に参加しました！ 昨年に続き2回目の参加です。
2019/9/15 AtCoder Beginner Contest 141で黄色になりました。 黄色になるまでにどんなことをしたのか書きたいと思います。
9/18-9/20に行われた会津大学競技プログラミング合宿2019に参加してきました。
JAG夏合宿2019にチームEldoradoとして参加しました。 チームメンバーは、ニクロー、まほろば、NOSS Day1の記事はこちら Day2 朝が早いのでちょっと眠たい。同室みんなで朝食を食べに行きました。 コンテスト コンテストリンク:https://onlinejudge.u-aizu.ac…
2019/9/14に行われたJAG夏合宿2019 Day1にチームEldoradoとして参加しました。 チームメンバーは、ニクロー、まほろば、NOSS Day1 コンテスト コンテストリンク:https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day1 Aをまほろば、Bをニク…
問題 自然数 を 進数で表したときの桁和を とするとき、 を満たす最小の を求めよ。 問題リンク：ABC044 D 制約 解法 条件をまとめると、 となるような を探せばよい。 ここで2つの式の差をとると、 となる。 は必ず を因数に持つことから右辺は で割り切れ…
問題 頂点 辺の無向が与えられる。最初、 番目の頂点には 人の兵士がおり、各兵士は隣接する頂点に移動するかその場にとどまるかを行う。ただし、兵士が移動できる辺の本数は1本までとする。 すべての移動後、 番目の頂点にいる兵士の人数を となるようにで…
問題 ICPC Europe Northwestern Regional 2012 A V頂点E辺の有向グラフが与えられる。このグラフ上で始点から終点への2本のパスを作る。ただし、2つのパスは始点と終点以外で同じ頂点を共有しないようにする。このとき、パスに使用される辺のコストの総和を…
問題 ICPC Regionals 2011 Europe - Northeastern の問題 問題リンク：UVa Live Archive 5920 - Kingdom Roadmap N頂点の木が与えられる。どの1つの辺を取り除いても全体の連結性が保たれるように辺を追加するとき、必要な辺の最小本数とその追加する場所を…
問題 問題リンク：There is No Alternative N頂点M辺の重み付き無向グラフが与えられる。最小全域木を構成するとき、どのような構成でも必ず使用するような辺の本数とそのコストの総和を求めよ。 解法 最小全域木に1つ辺を追加したとき、その辺によって作ら…
2019/7/12(金)に行われたICPC2019国内予選にチームEldoradoとして参加しました。 チームメンバーは、nicklaw、mhrb、NOSSです。 チームメンバーの参加記 - ICPC2019 国内予選 参加記 - まほろば精進日誌 結果 ICPC2019順位表 ABCD4完で順位は41位でした。学…
問題 問題リンク：ばらばら饅頭 解法 各重さの饅頭の個数を状態に持ってメモ化再帰をすることを思いつくが より、最悪 程度のパターンが存在するため厳しい。 パターンを減らすため、先に決めて損のない組み合わせを貪欲に取り除いておくことを考える。する…
問題 問題リンク 解法 訪れる順によって移動時間が変わる。一方、いままで訪れた蔵が同じであれば次に移動するときにかかる移動時間も同じである。 よって、今後どう移動するかはいままでの経路順によらないので、訪れた蔵の集合と現在地のみを状態として持…
問題 問題リンク 解法 ある区間内の山をすべて重ねたとする。このとき山の順序は変わらないので最終的にできる山の状態は、その重ねる順序によらない。 よって、区間を決めれば操作順を無視できるので、その最小コストのみが分かっていればよい。また、ある…
ICPC模擬国内予選2019にチームEldoradoで参加しました。 ABCD4完で順位は参加資格有17位でした。 順位表：2019/Practice/模擬国内予選/順位 コンテスト中の動き Aをmhrbさん、Bをニクローさん、Cを僕が読む。 Aをmhrbさんが一瞬で通す。Bの考察が完了してい…
atcoder.jp コンテストお疲れ様でした。 A - Favorite Sound (100) A - Favorite Sound A/BとCの小さいほうが答えになります #include <bits/stdc++.h> using namespace std; int main() { int a, b, c; cin >> a >> b >> c; cout << min(c,b/a) << endl; return 0; } B - K</bits/stdc++.h>…
森に枝を挿すと木になる 問題概要 N頂点M辺の森が与えられます。頂点には0から N−1の番号がついています。辺(xi, yi)は頂点xiとyiをつなげています。 各頂点iには aiという値が定まっています。 あなたは与えられた森に辺を追加して連結にしたいです。 辺を…
全国統一プログラミング王決定戦本戦に参加してきました。僕がどんな感じだったか書き残しておきます。 昼食 ゲン担ぎで"カツ"を食べました。そういえば某アニメでも決勝直前にみんなカツ食べてましたね。 昼食情報です pic.twitter.com/UYoBA4Pz0d— NOSS@日…
全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder 全国統一プログラミング王予選に参加したので、僕のコンテスト中の思考の過程を垂れ流しておきたいと思います。 A - Subscribers (100) 求めたいのは重複の最大と最小。最大…
CatChecker | Aizu Online Judge 問題概要 文字列Sが与えられる。Sが猫の鳴き声か判定したい。猫の鳴き声は次のように定義される。 空文字列""は猫の鳴き声 X,Yが猫の鳴き声ならば、'm'+X+'e'+Y+'w'は猫の鳴き声 以上で定義されるものだけが猫の鳴き声 Sが猫…
