オンサイトで未確認

ukuku09の活動記録。

ACM-ICPC 2018 Asia Yokohama Regional Problem E - Eulerian Flight Tour

問題概要

連結とは限らない $n$ 頂点 $m$ 辺のグラフ $G$ が与えられる。$G$ にいくつか辺を付け足して連結なオイラーグラフにしなさい。多重辺・自己ループは許されない。

制約

  • $3 \le n \le 100$
  • $0 \le m \le \frac{n(n-1)}{2}$

コンテスト中にした考察

以下、入力 $G$ の奇数次数頂点を黒、偶数次数頂点を白と書く。

 

まず「グラフがオイラーグラフ $\iff$ グラフに含まれるすべての頂点の次数が偶数」なので、問題文は「黒の次数を奇数・白の次数を偶数増やして、連結なグラフにしなさい」と言い換えられる。すると、$n$ が奇数のときは完全グラフ(すべての頂点の次数が$n-1$(=偶数))を作ればよいので、$n$ は偶数としてよい。

$G$ が連結な場合は簡単に解けると勘違いしていたので、非連結な場合を考えた。非連結な場合、

  • 連結成分がすべてオイラーグラフの場合
  • 連結成分がすべて非オイラーグラフの場合
  • どちらもある場合

が考えられる。

すべてオイラーグラフの場合が解けると嬉しそう。オイラーグラフが3つ以上ある場合は各オイラーグラフから頂点を1つずつ選んでサイクルを作ればよい。2つの場合、どちらも孤立点でなければそれぞれから適当な2頂点を選んで下図のように繋げばよい。

f:id:ukuku09:20181213130105p:plain
どちらかが孤立点 $x$ の場合、もう一方の連結成分 $C$ の頂点数は $n-1$(=奇数)なので、$C$ の頂点を使って完全グラフを作るとオイラーグラフになる。$C$ が完全グラフでなければ、完全グラフにする過程でどこかの辺に孤立点 $x$ を挿入すると、連結なオイラーグラフが作れる。$C$ が完全グラフの場合、ある $v \in C$ と $x$ とを繋ぐと必ず $v$ の次数が奇数になってしまうので、連結なオイラーグラフを作ることはできない("-1"が答え)。

オイラーグラフと非オイラーグラフがどちらもある場合、オイラーグラフ $C$ を1つ選んである $v \in C$ とすべての非オイラーグラフの黒との間に辺を張って $C^+$ を作ると、黒は必ず偶数個ある(握手補題)ことから、$C^+$ は連結なオイラーグラフになり、全てがオイラーグラフの場合に帰着できる。

オイラーグラフしかない場合、最も奇数次数頂点の少ない連結成分を1つ選んで下図のように繋げばよい(橙は選んだ連結成分の黒の集合、青はそれ以外の連結成分の黒の集合)。これも握手補題から各黒の次数は奇数増える。

f:id:ukuku09:20181213184228p:plain

非連結な場合が解けたので、連結な場合を考える。コンテストではこれが解けずに終了した。

連結な場合の解法

PFN企業見学の待ち時間に聞きました。待ち時間に問題解説が生えるのはPFNだけ!

 

$G$ の補グラフ $G^c$が 黒を奇数個含む連結成分を含む場合(例えばサンプル2)、答えは"-1"。

それ以外の場合、$G^c$ 上で全ての黒がちょうど1回ずつ端点になる(黒の数)÷2本のパスを適当に引き、奇数本のパスに含まれる辺を $G$ に追加すると、$G$ を連結なオイラーグラフにすることができる(!!!)。

$G^c$ が下図のような場合の例を示す。

f:id:ukuku09:20181213175106p:plain

黒は6個あるので、黒を両端点とする適当なパスを3つ選ぶ。

f:id:ukuku09:20181213175117p:plain

下図に奇数本のパスに含まれる辺を実線で示した。これらの辺を $G$ に追加すると、$G$ は連結なオイラーグラフとなる。

f:id:ukuku09:20181213175049p:plain

コード

上の考察通りにやったら結構長くなったので省略。実装が下手。

反省

聞いた瞬間確かにすぎて蟹になったんですが、5時間かけて思いつかないの頭が悪すぎて辛いです。やっぱり普段からちゃんと競プロやってないとダメなんだろうなぁ。

 

UVALive 7724 - Regular Number

思いつけばそれほど難しくないと思う。

問題概要

長さ $N$ の数字列にマッチする正規表現と長さ $5*10^6$ 以下の数字列が与えられる。正規表現にマッチする数字列の部分列を左から順に答えよ。

考察

$N+1$ 個の状態を一列に並べたオートマトンを考える。$i$($0 \le i \le N$) 文字マッチしているのをオートマトンの状態 $i$ にいると考えると、$j$($1 \le j \le N$)文字目の正規表現は状態 $j-1$ から状態 $j$ に進めるかどうかを決めるラベルとなる。

各数字についてどこにラベルがあるかと今のオートマトンの状態をbitsetで管理してやると、ビットアンドとビットシフトを組み合わせて始点の異なる複数の部分列のマッチング状態を一度に扱うことができる。

gist4297e823efc52ece391983f11374e1ad

UVALive 6070 - Conquer a New Region

簡単な問題しか解けない。マスコットだからね。

問題概要

頂点数 $N$ の木が与えられる。木の各辺には容量が設定されており、頂点 $u$ から頂点 $v$ へのスコアは $u-v$ パス上の辺の容量の最小値で定義される。

頂点 $w$ を一つ選んで、他の頂点から $w$ へのスコアの和を求めたとき、その最大値を答えよ。

解法

全方位木DPかと思ったけど、それでは無理だとbeetくんに教えてもらう。

辺を容量の降順でソートしておくと、辺 $i$ が2つの連結成分 $x,y$ を繋ぐとき、各連結成分に属する頂点に入るスコアはそれぞれ $size(y)*c_i,size(x)*c_i$ だけ増える。

連結性の管理と連結成分に属するすべての頂点に一度にスコアを加算するには、Union Findを応用してやると良さそうだと気づけば後は簡単。

 

giste2a3757a4faf918f4ea941df4138c4da

ACPC2018参加記

ククク…、私は大悪魔ウクニキア!

9月19〜21日に実質私主催(大嘘)の競プロ合宿、ACPC2018に参加したわ!

参加してくれた人間ども、遠方からはるばるご苦労だったわね!

作問の話

今年はあんまり参加しなかった。

というか気づいたら問題の枠も埋まってたし、テスターの数も足りてたからわざわざやる気にならなかった。

優秀な人材が多くて、我が部は安泰ね!

Day 1

何も覚えてない。btkさんと少しアズリムの話をしたんだっけ?限定Tシャツ早く欲しいね(9/22に届きました)。

・・・

Bが異常に難しすぎるんだよな。普通に制約を見逃していたので、適当考察でサンプルを合わせにいったらACした。

Dが右手法で解けそうということで、やなさんに丸投げする†悪魔的行為†。

Eを他のチームがバンバン通し始めたので、焦燥感に駆られながらもなんとかDPで解けそうな形に持って行けたので、適当にごにょごにょしたらACできた。よかった。

やなさんD頑張ってくれたのに協力できなくてごめんね><

・・・

TIkeさんとかolpheさんとかgoodbatonさんと話した気がする。E貪欲マジ?

beetくんとうしとそすうさとらーめん食べに行ったら8/31で閉店しててウケた。結局幸楽苑で味噌ねぎらーめんを食べた。今週2回目。会話の内容を全く覚えていない。

Day 2

なんかT◯1192916とかおるふ◯がすれ違うたびに「おっ、うくさんじゃ〜〜〜〜ん」とか絡んでくるので構ってあげた。私は優しいからね。

・・・

ジャッジだったけど、実はAしか作っていないので一瞬で仕事が終わった。ちなみにその問題がこちら↓

https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2018Day2/problems/A

Aということで解法一瞬問題を作ったつもりだったが、オンサイトでは1分を切るチームはいなかった。私の文章力に惹かれて熟読してしまったのかもしれない。

暇だったので作問作業で解かなかったFを解いた。微分?そんなものはWolframに投げればいいんだよ。

そのあとは先日初披露されたアズマリム のオリジナル楽曲「人類みなセンパイ!」を聴きながら時間を潰した。とりあえず人類みなセンパイ!は神曲だと思う。

・・・

冷静に考えて、あの日の懇親会はマジでヤバイ。

あまり飲酒しなさそうなメンツのテーブルだったから、わざわざはじさんを誘って一緒に飲もうとか言っていたのに、どうしてあんなことになってしまったのか…。

原因は明らかに私の後ろにセルフサービスの果実酒が置かれていたことと、Ti1192916があそこにやってきたことだと思う。私は悪くない()。

というか、人間どもがアズリムのことで私をいじりすぎなのが悪いんだよな。本気ではないとはいえ、まさかガチ恋口上をやる羽目になるとは私も思わなかった。確かbtkとかいう奴に煽られたんです。私は無罪なんです!(いや悪魔的には有罪の方が美味しい?)

「まっすぐ立てるんだよなぁ!」「まっすぐ歩けるからまだいける!」とか言ってたけど、あれダメだよね…。

とはいえ私は帰る頃にはTIkeさんとの烏龍茶を巡る旅が効いてだいぶマシになっていた。TIkeさんに圧倒的感謝。

c7くんがベロンベロンに酔っていて連れ帰るのが大変だった。最終的に彼の友人に引き渡したのだが、何度も「えっと、誰?」みたいな扱いを受けた。大悪魔の顔を忘れるとはなんて恐れ知らずなのかしら?

Day 3

またなんかTi1192◯16とかお◯ふぇとか半角カナの人に絡まれたので構ってあげた。大悪魔は実は面倒見が良いのである。

うしとそすうさとチームを組んだ。ちなみにチーム名はacpc_aizulimだが、アズリム要素を入れることを最初に提案したのは私ではない。

コンテスト前にそすうさが「アズリムちゃん見たい」というので、適当にオススメ動画を選んで鑑賞会をした。アズリムはいつどこで見ても可愛いなぁ〜〜〜。

・・・

なんかこの日はよく覚えてる。なんでだろう。

私は普段のコンテストでは実装をbeetくんに投げているので、この日はうしさんに全部押し付けた。

Cはまあはいなので、うしがAを解いたタイミングを見計らって引き渡した。

Bが難しい。全然わからん。なんでどこの大学もBに罠を置くのか。うしもわからんとか不可能じゃんという気持ちになっていたら、うしがD解けたらしいのでDを解かせた。

そすうさにEの概要を聞いたらこれもまあはいだったので、うしに丸投げする。WAったのでコードを見たらなんか激ヤバなミスしてて、なんでサンプル通る念という気持ち。

私がBで遊んでいたらうしがGを通したので、みんなでBを考える。結局クエリ平方分割で解けるという話になって、それでうしが通したけど流石に想定じゃないよなぁと思った。

残り時間が少なくなってきてFいけるかなぁという感じだったんだけど、そすうさがいろいろ考察を進めてくれていて、なんかごちゃごちゃやっていたら、場合分けシミュレーション解法に落ち着いてこれFまじ?と言いながら実装を見守った。

ラスト1分を切ってうしがFを通し、オンサイト逆転1位を勝ち取れた展開はめちゃめちゃ熱かった。

・・・

解散は意外とあっさりしていたのであっさり終わった。

まとめ

疲れたぁーーーー!!

JAG合宿と合わせて6日も合宿コンテストしたわけだから流石に疲れたわ。

1番の思い出は、けんちょんさんとTIkeさんの「うくさん、昔は競プロ美少女大悪魔だったのに、今じゃただのアズリム大好きおじさんになってしまった」という言葉。

なんでよ?!今でも十分美少女でしょー!?

本当にお疲れ様でした。

ちなみにこの翌日のコドフェス予選は寝てたから出忘れた。

 

JAG夏合宿2018参加記

私は†胡桃沢=ウクニキア=マクドウェル†…。

9月15〜17日に行われたJAG夏合宿に、この私も顔を出してやったわ!

我が忠実なるシモベの頼み事とはいえ聞き入れてやるなんて、私の心はなんて広いのかしら?

合宿前

私の愛すべき後輩であるアズリムが、16日のRAGE 2018 Autumnに参加すると知る。

しかも実質アズリムの初ライブとなるオープニングライブでは、待ちに待ったアズリムのオリジナル楽曲「人類みなセンパイ!」が初お披露目されるとか。

そんなアズリムの晴れ舞台を競プロ合宿のせいで見にいけないと知って、すでに競プロモチベが皆無だった私の精神はズタボロになった。

Day 1

高速バスで新宿まで移動。

今日から3日間、オリセンとかいう監獄に閉じ込められるんだなぁと思うと心が暗くなる。

明日のRAGEには行けないにしても、せめて東京まできたんだから松屋くらいには行っておきたいと思い、傘のないはじさんを連れて雨の中松屋へ向かった。頼んだのはもちろんプレミアム牛めしととろろ、なぜなら私もアズリムのセンパイだからです。

・・・

コンテストのことは忘れた。

久々のチーム戦だったから、いろいろ動きを見直す感じだった気がする。

いつものごとくbeetくんがバンバン解法を生やして実装をしてくれたので、私は椅子を温めることに専念した。

・・・

RAGEからは気持ちを切り替えたつもりだったが、アズリムの投稿を見て我慢してた感情が爆発する。

コンテスト終了1時間前に抜けられれば間に合うのでは?と思い、5000円でbeetくんを買収しようとしたが一蹴される。え〜ん><

アズリム、心の中で応援してるからね・・・。

Day 2

コンテスト中は当然スマホをいじるわけにはいかないので、コンテスト前にアズリムにリプしたいなぁという気持ちでギリギリまで粘ったが、さすがに朝の10時は早すぎた。

・・・

コンテストのことは忘れた。

最終順位は6完5位。当然私は1問も解いていない。問題文に一通り目を通したあとは机の掃除を頑張った。まあEとFは少し貢献したかもしれない。

結局ラスト1時間はAC数を増やすことができず、beetくんが「これならうくさん抜けてもよかったね」みたいなことを言ったので「それは言っちゃダメでしょ…」という気持ちになった。

ちなみに昼食のお弁当は牛丼にした。JAGもなかなかわかってるじゃないか。

・・・

やはりコンテスト中にアズリムがツイート+リプ返をしていた。リプいいねをもらうために応援しているわけじゃないけど、やっぱり一言応援リプを送りたかった。

解説中にオープニングライブが始まったので、AbemaTVで視聴した。おかげで解説のことは覚えてないが、画面の向こうで一生懸命歌とダンスを披露してくれるアズリムにとても心打たれた。

「人類みなセンパイ!」の曲調は明るく、いつも元気なアズリムにピッタリだと思った。しかし、歌詞はまるでセンパイたちのためだけに書かれたかのようなとても胸を打つもので、喜びと感謝の気持ちでいっぱいになった。

大会はアズマリム ・もこ田めめめペアが大健闘してくれたので見ていてすごく楽しめた。大会終了時には二人の距離が縮まったようで、私も嬉しい。

Day 3

コンテストのことは忘れた。

最終順位は9完4位。もちろん私は解いてない。問題文を読んで概要をまとめる作業をした。

Hが明らかにLPの見た目をしているので、「シンプレックス法があれば解けるでしょ」とか言っていたが、シンプレックス法は落ちる想定だった。世知辛い。あとフロー怖い。

Kは実質PCK過去問だったが、その時と全く同じ嘘解法を生やした。成長してない。

・・・

解説終了後すぐに帰路についた。さっさと帰って自分の部屋のベッドで寝たかったし、なによりさっさとWi-Fi環境でRAGEのアズリムを振り返りたかった。

人類みなセンパイ!は冗談抜きで神曲なので全人類が聴くべき。

まとめ

JAG夏合宿おつおつおー!

まあ私はいつも通り我がシモベたちを手足のごとく働かせたけど、やはり優秀ね。さすがは私のチームだわ!

精進のモチベとかはもう完全にないし、私はもう雑用とかサポートとかに回ったほうが良さそう。というか去年からずっとそうなんだけど。

最後に一つ言いたいことがあるわ。未だにアズリムを知らぬ愚かな人間どもよ…、人類みなセンパイ!を聴いて、アズリムを見なさい!!

 

AOJ 2691: Cost Performance Flow

久々にフローの問題を解いたうくー!

 

……とは言っても本質であろう「解析的に解く」という考察はbeetくんに聞いたのでまぁはい。

 

問題概要

https://onlinejudge.u-aizu.ac.jp/#/problems/2691

 

辺に向きとコストと容量のついたグラフがあります。sからtへフローf_{s,t}を流します。このとき、

B(f_{s,t}):=C(f_{s,t})^2+(M-F(f_{s,t}))^2

で定義されるバランス関数B(f_{s,t})を最小化するf^*_{s,t}を求め、B(f^*_{s,t})を既約分数で出力してください。

ここで、Ms-tフローの最大流量を、C(f_{s,t})f_{s,t}のコストを、F(f_{s,t})f_{s,t}の流量を表します。

 

みたいな(日本語ができないので許して

 

解法

最小費用流(というかPrimal Dual)の気持ちになると解けます。

 

こういうのは解析的に解く(beet談)らしいので、B(f_{s,t})が下に凸の関数ならその極小値を求めたいです。(実際B(f_{s,t})は下に凸な関数です。)

ところで、C(f_{s,t})は流量F(f_{s,t})の関数とみなせるので、以降F(f_{s,t})FC(f_{s,t})C(F)と書きます。(ついでにB(f_{s,t})B(F)で書きます。)

Primal Dualで新たな最短経路に沿ってフローを流すたびに得られる、それまでの流量FとコストC(F)をグラフ(グラフ理論の方でない)にプロットします。

f:id:ukuku09:20180527113449j:plain

こんな感じになります。

最小費用流の気持ちになると、新しい最短経路に対して流量とコストは比例の関係にあるので、ある区間\alpha \le F \le \betaでは

\displaystyle C(F)=\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)

です。

この折れ線上にB(F)を最小化する点があるはずなので、上の式をB(F)に代入して微分します。

\displaystyle B(F)=\left\{\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)\right\}^2+(M-F)^2

\displaystyle B'(F)=2\frac{C(\beta)-C(\alpha)}{\beta-\alpha}\left\{\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)\right\}-2(M-F)

で、B'(F)=0として整理すると、

a=\beta-\alpha

b=C(\beta)-C(\alpha)

c=C(\alpha)

\displaystyle F=\frac{a^2M+b^2\alpha-abc}{a^2+b^2}

が得られるので、これが\alpha \le F \le \betaを満たすかを調べてえいえいすれば良いです。

どの区間も不等式を満たさないなら、プロットした点でのB(F)の最小値が答えです。

 

補足

答えを既約分数にしないといけないので、式変形とかしないといけないくて面倒くさいです。多分その辺を適当にやったからだと思うんですが、オーバーフローしたので†__int128_t†を使って無理やり通しました。

 

提出コード

AOJ 2691: Cost Performance Flow

 

RUPC2018参加記

〜♪(あのBGM)

ぬぁ〜はっはっは〜!!私は「そういえばガ◯リール・ドロップアウト見たんですけど、赤い子の名前ずっとウクニキアだと思ってました!」ってn回言われる大悪魔ァ…†胡桃沢=ウクニキア=マクドウェル†!!

今年もシモベどもの忠義を確認し彼らを労うため、そしてさらなる戦力の増強、支配圏の拡大のために、立命館大学へ出向いてやったわ!感謝しなさいよね〜♪

Day ?

作問した。

とりあえず†悪魔的実装†をすれば解けることがわかったので、無理やり問題セットにねじこんでおく。

後になってbeetくん(@beet_aizu)と怒髪さん(@dohatsutsu)がより良い解法を出してくれたので助かった。

Day 0

1週間くらいじっかぐらし!を楽しんだ。

ARC開始直前にbeetくんになりすます†悪魔的行為†。

そのまま迎えたARCは1完。頓死したクズですが。(構築ゲーは方針ガチャなので)

気分が最悪になったので寝た。

Day 1

うしさん(@ei1333)と一緒に新幹線乗車AC。

新幹線の中で前日のARCトーク

うしさんはEを解いていたので、うしさんに方針を確認しながらEを考察。

うしさんから解法ACをもらう。やったぜ。

ukuku09.hatenablog.com

 

南草津駅でbeetくんと合流。らてまるた(@LatteMalta?)がいなかった。

にぼった。

 

自己紹介フェーズはまぁはい。(はいなので)

「なぁ〜はっはっは〜!私はこの合宿を掌握するもの、†胡桃沢=ウクニキア=マクドウェル†!手始めに我が研究室のシモベにAOJのシステムを書き換えさせたわ!せいぜいpracticeでしっかりチェックしておくことね!」

みたいなことを言った気がする。

 

「チームは決めてこない。誰と組もうが最高のパフォーマンスを出す。それだけよ。」

なので会場でチームメンバーガチャ。tsutajさん(@_TTJR_)とwhesonさん(@wheson)さんに決まる。

レート的にtsutajさんが一番強いので椅子を温める担当をしようとしたが、なぜかCをやることになってしまう。

 

B読めねェ…。

Cは見た感じ解けそうで、Bが読めなかったらしいので変わったのだが、読めねェ…。

1:30/3:00をBに溶かす。

「この考察だとaを使う必要がなくて、必要のない入力をさせる問題はマジでクソなんですよね〜」

EGを通したtsutajさんがDの解法をくれたので気分転換に僕が実装。AC。

すかさずtsutajさんがFを通す。

3人でBを考える。tsutajさんが最初の方針があってたのでは?と言い出してOutputを見たらああああああああ。AC。

全完しました。

 

懇親会は多くのシモベと話した。まったく、上に立つってのも大変よねぇ〜。

 

運営特権で立命館の合宿施設を使わせてもらった。

留学生のlamさんの分の宿泊費を立て替えたことを英語で伝えようとした結果

「Hey, I paid... your あー... charge? fee? うー...beetく〜ん」

新幹線の中でうしさんに解法ACをもらったARC093のEを実装した。教訓「modを取り忘れない」。

りゅうおうのおしごと!最終話を見ようと思ったら、お子ちゃまbeetくんに「でんきちゅいてるとねれないのぉ〜!」って言われたので、真っ暗な部屋の中で見る羽目になった。

Day 2

ジャッジ陣なので準備のほうをね。

前日に決めた集合時間に間に合ったのがろーるさん(@rollman054)だけで怒ってた。

5時間セットというのもあってか、問題文の印刷に紙を無限に消費してしまった。紙の大切さを知った。

問題文の仕分けに人力セグメントツリーと化した僕が投入され、効率的なマージを実現した。が、ちょっと間違えたためア。

 

なんかチノちゃんが来てたので記念撮影した。

btkさん(@btk15049)が「うくさんはコスプレしないんですか?」とか言っていて意味不明だった。なんですでに美少女で完璧なルックスを持つこの私がコスプレなんてしなきゃいけないのよ?

 

今年は風船を配らなかったので正直やることがなくて暇だった。

桁DP初心者なのでDay1Fをバグらせてたらbeetくんに「状態の持ち方がわかったらあとはやるだけじゃん」とか言われてしまった。

4時間くらいで全完チームが出て「「おぉ〜」」とか言ってた。

終了間際にらてばたぱるチームから解法を文章で書いた提出があってウケた。

 

A問題文担当としては、AのSuccess Rateが100%じゃなかったことに驚いた。

ei1333ってなんやねん。

Lの解説は逆に混乱を招いたかもしれなくて申し訳ナス。

 

懇親会はまぁらて。ぽまえ〜って感じだった。

うしさんが共食いをしてる証拠映像を抑えた。

 

立命館の合宿施設を追い出されたのでネカフェった。

dアニメストアでよりもい最終話を見たけど泣かなかったです。

Day 3

コンテスト前は特に何もなかったが、らてうしがbtkさんからNEW GAME!を買い取ってていーーーなーーーって思いました。

 

チーム決めの結果、yebiさん(@yebis7)といらいざさん(@Eliza_0x)と組むことになった。なんか僕のレートが一番高いことになっていておかしくないですか?まぁなんだかんだいって任意の人間は僕より強いみたいなところがあるため。

 

C通らねェ…。

Cはやればできますとか言っといてWAを量産する†悪魔的行為†。結局通ったのはコンテスト開始から1時間後だった。

D通らねェ…。

DはDPのDなのでDPを考えたが通らなくて辛かった。提出デバッグという†悪魔的行為†。結局通らないのでネガティブな発言をしていたところ、いらいざさんに

「なんか実際はそんな感じなんですね」

って言われた。は?なるほどね。(わかるよ)

残り時間が30分を切り、気分転換にFを読んだらえーこれ最小カットやるだけじゃ〜ん。ノリで実装したらACした。

残り10分を切ったあたりでEも読んだらなんかめちゃくちゃ既視感。これ去年自分がRUPCで出そうとしたやつまんまじゃん!!となって急いでコードをコピペして入出力を修正してたが間に合わなかった。あとで通った。

 

全完チームが続出するなか4完で終わってしまい、チームメイトにとても申し訳なかった。

 

疲れたので解説終了後は特に誰と話すでもなく帰路についた。

人生において重要なことは、コピペでAC数を稼ぐことではなくNEW GAME!新刊を読むことなので、南草津駅近くの本屋でNEW GAME!新刊を購入した。

ろーるさんとkzyさん(@kzyKT_M)と一緒にご飯を食べにきあ。美味しかったです。

感想

とても疲れました。

最後に

クックック、なーはっはっはっはっはー!!愚かな人間どもよ、我が暗黒の力、思い知ったか!

……へ?ウクニキア戦犯しかしてないじゃん、ですって?フン、当たり前でしょー!それが†悪魔的行為†ってやつよ。そんなこともわからないの?これだから下等生物は困るわよね〜。

いい?命が惜しかったら9月下旬に開催されるであろう会津合宿にも参加すること!我が城で待ってるわよ。