Dinic法について

理解にかなり手間取った&面白かったのでメモ。 アルゴリズム やっていることは、「長さが短い順に増加路を使っていく」というだけ。 以下、頂点数 、辺数 、始点 、終点 のネットワークを考える。残余グラフを構築しておく。 増加路がなくなるまで、以下を繰…

JOI2020春合宿 参加記

結果から言うと、5位で代表にはなれませんでした。 以下、日記です。(全てその日のうちに書いたもの) Day0 朝起きると体調がよろしくない。本選の時もそうだったので情報オリンピックに呪われているんじゃないかと思う。 Library Checkerを埋めて「やがて君…

JOI'17春合宿 Dragon 2

幾何パートとデータ構造パートに分かれている問題。幾何パートで下手な考察をして、場合分けと実装を爆発させてしまった。 データ構造パートで解説と違うことをしていたので、主にその部分について整理する。 問題 atcoder.jp 解法 解説にある最初の満点解法…

JOI'17春合宿 Port Facility

天才数え上げな見た目をしているのにゴリゴリデータ構造ゲーに落ちるという面白い問題。 かなり苦戦して通したので整理しようと思う。 問題 atcoder.jp 小課題1 条件を満たすように、区間の集合を2つのグループに分けた時の通り数を求める問題。 問題文にや…

JOI2020本選 参加記

去年 ta1sa.hatenablog.com 0日目 夜に謎の熱っぽさに襲われ、頭も痛かったので厳しい気持ちになった。 1日目 朝起きたら体調がマシになっていたので、難易度9バチャをする。しかし、1年前に自力で解けたTentsという問題が全然解けず、冷えた。 普通に一人で…

10/27-11/9

文化祭でまともに競プロができていなかったので2週まとめて。 AtCoderのレートがいっぱい上がったしHTTFもユース枠で通ったのでよかった。 出たコンテスト AGC040 90位 2043->2111 HTTF2020予選 73位 第2回全統プロコン予選 102位 2111->2163 解いた問題 ABC…

10/20-10/26

1ヶ月続いたけど既にさぼりそうな気配が出てきている。 競プロで冷えただけの週だった。頭の疲労を効率的に取れるようになりたい。任意のコンテストが塾の後にあるのでまともに頭が働かない... 出たコンテスト CF#596(Div.1) 589位 1938->1866(???) IOI2014 …

10/13-10/19

今週はvirtualはお休み(毎週お休みしそう)。 CFでレートを下げただけの週だった...。 出たコンテスト KUPC2019 34位 CF#592(Div.2) 372位 2017->2008 CGR#5 2498位(????) 2008->1908 CF#593(Div.2) 335位 1908->1938 ABC143 23位 解いた問題 KUPC2019-D MaxM…

10/6-10/12

出たコンテスト IOI2013 Day 2 Virtual 今までやった5時間セットで一番成績がよかった。 100+100+63=263点、Day1と合わせて430点、銀の真ん中らへんなので適正という感じ。 ~0:30くらい 1問目を読むと、30分で76点、定数倍が軽ければ100点が取れる解法がわ…

9/29-10/5

この場所を有効活用したいと思ったのでばちゃの結果を書くことにした。代表になれないのにIOIばちゃをする人になった(大学生になったらどうせ解かないし...)。 できる日は5時間ばちゃをやってここに記録するようにしたい。 出たコンテスト CF#589(Div.2) 3完…

9/22-9/28

ブログっぽいことをしようと思いました。 出たコンテスト CF#558(Div.1) 2完 2018->2095 PG BATTLE 結果不明 ABC142 6完 1982->2027 解いた問題 手応えのあった問題だけ。 JOI2009春 1-2 Stamps https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-…

AtCoder黄色になりました

青になってから半年たたずになれるとは思いませんでした。やったね。AtCoder黄色になりました!!!!! pic.twitter.com/zjv7M4c6Ig— たいさー (@ta1sa_) 2019年5月4日 黄色になるために自分が役に立ったと思ったことを列挙します。大体は他の人もブログに…

JOI2019春合宿 参加記

Day ? 直前に2018のVirtualをやったら3完だったので、今年もそのくらいできるかな〜と言っていた。1ヶ月前くらいから難易度10埋めをしていた。対戦よろしくお願いします pic.twitter.com/Eg01mJiiWt— たいさー (@ta1sa_) 2019年3月19日 Day 0 双子から誘われ…

JOI2018/2019本選 参加記

あったことを羅列します。 1日目 10時くらいに起きてTwitterを見つつ適当に出る。 北千住でTMJNと会ったので毒蛇の脱走の考察をするが、なにもわからなくなりやめる。TMJNが天才っぽいことをしていて天才。 会場に着くと同校が大量にいたので固まる。パズル…

ABC116-D Various Sushi

コンテストは2位でした うれしい 問題 atcoder.jp 考察 最終的に答えに影響するのは「おいしさの和」と「種類数」なので、考えやすい「種類数」を軸に考察していきます。まず、最適になりうる種類数は、「おいしさの大きい順に貪欲にK個取った時の種類数」以…

JOI2018/2019予選 参加記

開始前 ・SSSS.GRIDMANを見る ・眠かったので音ゲーをして目を覚ます 1問目 ・見る ・数学ゲーっぽくて嫌だなあとなる ・ログイン日数を固定するといい感じになるので、書く ・WA(は?) ・コードを睨むとオーバーフローしているので、直す ・AC(05:09) 2問目…

picoCTF 2018に出た

10110点で終了時730位くらい。 Warmup以外について雑に書きます。 Forensics Desrouleaux(150) 画像を見れば答えが分かるので答えていくだけ。もう少し問題が難しくなるとスクリプトを書いたほうがよさそう。 Reading Between the Eyes(150) Hintsにあるよう…

CyberRebeat CTFに出た

CTF

結果 2506pts/37位 解ける問題は全部解けたのでよかった(?) 解けた問題について Simple Binary(Binary) 実行しても何も出力されないので、main関数の最後の方にブレークポイントを置いてみる。 rdiの辺りのメモリを覗いたら出てきた。 Rotation(Crypto) シー…

ABC106 参加記

実装力のNASAを感じたコンテスト。 A-Garden 問題 https://beta.atcoder.jp/contests/abc106/tasks/ghi_q 考察 (全体の面積)-(道の面積)を求めればいいので、 が答えになる。 41秒でAC。 実装 Submission #3027934 - AtCoder Beginner Contest 106 B-105 問…

ABC104 参加記

A:0:56 B:5:17 C:12:20 D:58:53 全完0WAで80位、今回はなかなか難しかった。 Aは場合分けをするだけなので省略。 B-AcCepted 問題 B - AcCepted 考察 の長さをNとする。 要するに、が ・1文字目が’A' ・3文字目〜N-1文字目の間に'C'がちょうど1つ含まれる ・…

JOI2009春合宿 Abduction

問題 https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day2_21.pdf 考察 まず、すぐに思いついたのは、 =今までに回曲がって、にいる時の移動の仕方の通り数 というDPだが、当然これでは間に合わない。 ここで、縦方向の移動と横方向の移動は互…

ARC068-E Snuke Line

解説ACの問題もどういう思考過程をすれば解けるか書いていこうかなと 問題 E - Snuke Line 考察 ・間隔がのとき、となるような名産品は絶対に買える! ・各名産品を区間の長さでソートしておくことで、間隔を短いほうから見ていった時に「絶対に買える名産品…

ABC103 参加記

結果 全完で321位 D: 36:56(2WA) C: 46:49 B: 48:20 A: 50:26 イキってDから解いてこれはひどい... A、Bは省略(両方全通り試した) C-Modulo Summation 問題 C - Modulo Summation 考察 ・すべてのの最小公倍数くらいまで探索すると良さそう ↓ 絶対TLEする ↓ …

JOI2011本選5 微生物実験

難易度9を初めて自力で通せました。うれしいね 問題 E: 微生物実験 (Bug Party) - 第10回日本情報オリンピック 本選(オンライン) | AtCoder 考察 「選んだの最小値がの平均以下」という条件は、「選んだの最小値*(個数)がの和以下」という風に言い換えら…

ARC026-C 蛍光灯

問題 C - 蛍光灯 考察 貪欲ではできなそう ↓ L区間が全て照らされているときのコストの合計の最小値 というDPを考える ↓ 右端の座標をキーにソートしておくと、dp[r]=min(dp[r],min{dp[l],dp[l+1],...,dp[r-2],dp[r-1]}+c) というように遷移させられるが、こ…

ABC099 参加記

結果 A: 0:39 B: 2:49 C: 56:39(2WA) D: 38:35 だめですね A,Bは省略 C-Strange Bank 問題 C - Strange Bank 考察 これよく見る大きい方から取っていく貪欲じゃーん ↓ サンプル3が通らない ↓ 反例があることが分かるので他の解法を考える ↓ dp[i]=i円を引き…

CODE FESTIVAL 2016 Elimination Tournament Round 1-A グラフ

問題 A - グラフ / Graph 考察 「どの頂点にも頂点S_iまたは頂点T_iから選ばれた辺のみをたどってたどり着けるようにしたいです。」 ↓ S_iとT_iをそれぞれ含む2つの木をもつ最小全域森(?)をつくるとよさそうだが、クエリごとにやっていては間に合わない ↓ 「…

codeFlyer-C 徒歩圏内

問題 C - 徒歩圏内 考察 全探索でO(N^3) ↓ s[i]=x[i]からの距離がD以内の場所 を保存しておくとよく使いそうなので二分探索で求めておく(これでO(N^2)) ↓ このままだと間に合わないので、iとjを決める二重ループを書いてみると、ループの中が ans+=s[j]-s[i]…

ARC098 参加記

結果 A: 6:09 B: 46:10 C: 1WA はい C-Attention 問題 C - Attention 考察 問題を読んだら全探索でできるとわかる ↓ 自分より東にある'E'の数/自分より西にある'W'の数を高速に求めたい ↓ 累積和 実装 #include<bits/stdc++.h> using namespace std; #define all(vec) vec.b</bits/stdc++.h>…

AGC024 参加記

結果 A: 3:37 B: 3WA C: 61:03 2完745位でぱふぉ1452 700点を通してこれとは... A-Fairness 問題 A - Fairness 考察 K≦10^18だから何か規則性がありそう ↓ 実験してみる ↓ 差の絶対値は変わらずに偶奇によって正負が変わるだけだとわかる ↓ AC 実装 やるだけ…