ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ICPC2021アジア予選 参加記

suzuken君、bayashiko君と「MSB」で出ました。

コンテスト前

模擬は13位でした。可もなく不可もなし。
前日は友人とvalorantをしていましたが、明日があるから早く寝ろと怒られました。彼は優しいのでモテると思います。

コンテスト

まずばやしこくんがA、すずけんくんがBを読み、自分はざっと後ろの問題の雰囲気を確認しました。
自分は英語を読まない担当だったので、すずけんくんが読んだBを共有してもらい、そのままAC。この時点で3位になり、順調にいけば弊学ライバルチームのgive usに勝てるとニコニコしていました。

その後は、へのさんのチームがGを通していたので、数え上げが好きな自分はGに特攻。ばやしこくん、すずけんくんはそれぞれ問題の翻訳を進めつつ、ACが出ている問題に手を出す、という形になりました。
G問題は明らかにDPであるとにらんでいましたが、ループができるパターンをうまく排除する方法が全く思い浮かびませんでした。ARCの問題の解説も見たりしましたが、めどが立たなかったため、一度離れてJを見ることに。
Jの嘘解法を思いつき、せっせと実装をしていました。
その間、ばやしこくんやすずけんくんはC,Dあたりとにらめっこしますが、完全な解法まではたどり着けず。刻一刻と時間だけが過ぎていきました。
コンテスト開始から2時間が経過し、自分が嘘解法を修正してJの解法を思いついたとき、Wavelet Matrixが必要になったので、「これはばやしこくんに"譲ってあげよう"」と思い、ばやしこくんを呼び寄せて解法を押し付け伝えてバトンタッチしました。
すずけんくんはその間にもDの考察を進め、開始から3時間後に無事ACすることができました。


G, Jは完全に炎上しました。G問題は全く考察が進まず、J問題は手元で生成したランダムケースですべてACしているにも関わらず、提出するとWAになってしまいます。
順位表が凍結するとき、give usチームは5完で10位にいたのにも関わらず、自分のチームはまだ3完でした。
さすがに全員疲れと焦りが出ており、微妙な空気が漂っていました。

残り30分くらいになり、急にGで困っていた部分を解決する方法が天から降ってきました。 必死で実装を進めていると、残り10分くらいでJ問題では悲劇が起きました。
なんと、Home画面に問題文の解釈に関するClarが届いていたのです。
今回のシステムでは、(少なくとも自分は)通知が来なかったため、全然気づいていませんでした。
ばやしこくんが「これ直すの無理だ…」と落ち込んでいましたが、修正を始めていました。
すずけんくんがCを進めながら、三並列で進めていると、残り4分で自分のGが通りました。
どうにか3完を阻止できたと、すずけんくんと二人で喜んでいると、なんと残り2分でJも通りました。
達成感と疲労感に包まれながら、コンテストはそのまま5完で終了しました。

結果として、5完・13位でアジア予選を終えました。

f:id:emtubasa:20220317030529p:plain

コンテスト後

gather townにて、いろいろな人と話しました。
noimiさんや熨斗袋さんにおめでとうを伝えたり、tossyさんと再会したり、人が多いところでミュートして静かに聞くモブを演じたりしていました。
最後には、むげんさんが募集していたGartic Phoneに参加しました。
競プロerが集まっていたため、AntsAnd GridEarsといった競プロ有名問がお題に出ていても、綺麗に伝わっていきました。感動。

おきもち

2019年のアジア予選では、パフォーマンスが全く発揮できず、自分の中で満足いく結果が出せませんでした。同大会に出ていたもう一つのチームは、オンラインで世界大会に出場できる結果を残したのもあり、自分のチームのコーチから煽られもしました。
2020年、早稲田の中で現状一番ともいえるチームに入りました。しかし、結果は予選落ちとなり、なんとも表現しがたい感情だけが募っていきました。
昨年3月、かっつくんとアジア予選のYes/Noをdiscordでしゃべりながら見ていました。来年は二人ともここに出られたらいいね~って話をしていたと思います。
その後、ばやしこくんとすずけんくんに誘ってもらいチームを組み、今年は再び国内予選を通過することができました。
今日のアジア予選まで、モチベーションが低下していたのもあり、あまり精進できていませんでしたが、何とか40チーム中13位という、とりあえずはいい結果を残せました。残り5分で2問を通し、Yes/Noで少しわかせることにもなりました。
しかし、ずっとライバル視していたgive usチームには、国内予選・アジア予選ともに勝つことはできませんでした。
J問題のClarがどうとか、なんとかかんとかいろいろありましたが、現在の自分の実力だとここからさらに+1問をそれなりの速度で解くのは難しいなと思います。結局、完敗でした。
いろいろありましたが、再びアジア予選の舞台に立って、ある程度の結果が残せたのはよかったです。現在の自分の実力を出し切ることはできたと思っているので、満足しています。
自分は早生まれなので、修士2年の来年度も出場することができますが、まだ出るかどうか決めていません。自分のモチベーションとも相談しつつ、のんびり考えていこうと思います。
ここまで読んでくださった方々、誘ってくれたばやしこくんとすずけん君、一緒に戦った早稲田のチームの方々、応援してくださった皆様、懇親会で話してくださった皆様、そしてコンテストを運営してくださった皆様、本当にありがとうございました。

ABC231 G - Balls in Boxes

問題
提出コード

解法

\prod _{i = 1}^{N} B_{i}の総和を求めて、最後に全パターン数N^{k}で割れば答えです。総和の求め方について考えていきます。

\prod _{i = 1}^{N} B_{i}は、N個の箱にあるボールB_{i}個からそれぞれ1個ずつ選ぶパターン数と一致します。
 \prod_{i =1}^{N}\ _{B_{i}}C_{1}ということです。

i個目の箱にあるボールB_{i}からボールを選ぶパターンは2パターンあります。
最初から入っているA_{i}個のボールを選ぶパターンと、新しく追加されたB_{i} - A_{i}個のボールを選ぶパターンです。
前者は明らかにA_{i}通りです。

N個の箱の中で、前者を選ぶグループを決めていきます。すると、前者を選んだ箱pにおける\prod A_{p}に、K回のボールの入れ方、および後者を選んだ箱のボールの選び方をかけたものを足していけば答えです。
新しく追加するボールの入れ方や選び方は、前者を選んだ数に依存します。なので、\prod A_{p}をあらかじめまとめて足しておきます。
これは、

  • dp[i][j] = i番目の箱までみて、j個の箱を前者として選んだ状態における、\prod A_{p}の総和

として計算していくことができます。

では、dp[N][i]にかけるべき数を計算していきます。やることは2つで、

  1. K個のボールのうち、N-i個の選ばれるべきボールの位置を決める

  2. 残ったボールを箱に振り分ける

です。

1つめについて考えます。まだ選ばれてない箱の番号が\{a,b,c\}だったとします。この時、K回の操作のうち3つをとってきて並べた列\{x,y,z\}を作ると、前から順番にa,b,cに割り当てることで、過不足なく数えることができます。つまり、K個の中からN-i個選んで並べるパターン数になり、\ _{K}P_{N-i}となります。

あとは2つめの操作です。残っているボールは、どの箱に割り当てても問題ありません。なので、残っているボールの手前から順に、N個の箱の中から1つ選んでいけばよいので、N^{K- (N-i)}が答えです。

よって、dp[N][i] \times\ _{K}P_{N-i}\times N^{K- (N-i)}を計算して足していけば答えになります。

感想

\prod _{i = 1}^{N} B_{i}をボールの選び方に帰着させる問題は今まで解けたことがなかったので、今回初めて解けてうれしいです。 

ICPC2021国内予選 参加記

解法への言及があります、ご注意ください
suzuken君、bayashiko君と「MSB」で出ました。AtCoderにおけるIDの頭文字をとってきたものです。
前日になって何故かスポンサーが突如ついたらしいです。

コンテスト前

コンテスト前日はPCを22時くらいにカバンにしまっていたので、手持ち無沙汰になりました。高校からの親友に電話して、一緒にスマブラをしていました。彼は最近競プロを始めたので、ICPCについて語りながらプレイしていると、スマブラでボコボコにされていました。

コンテスト当日、開始は16:30なのですが、お昼は外で食べようと思い、12時に着きました。が、全くお腹がすかないので、散歩をすることにしました。
理工キャンパスから本キャンパスへ行き、ふらふら歩いていました。
明日は早稲田祭があるらしく、いろんな学生が忙しそうに移動していました。僕には縁のない話です。
そんなこんなで1時間ほど歩き続けました。
帰り道、ドン・キホーテに寄り道をすると、アルフォートが70円弱で売っていました。ここに毒を盛れば、弊学の5チームを全て闇討ちできる!そう思い、ニコニコして購入しました。

14:00あたりから、ぽつぽつと人が集まり始めます。自分は、一旦同期の人達と雑談をしていました。その後、コーチをしてくださっているとまとさん、るぎうさんがいらっしゃって対応していると、同期に「敬語使えるんだ」と煽られました。そら使えますよ。
さらにしばらくして、1年生のserpent君が到着したので、感動しておー!となっていましたが、自分が名乗るのを忘れており、同期に笑われました。敬語は使えますが、自己紹介はできないみたいです。

人がたくさん集まり、それぞれの部屋で準備を始めている頃、お菓子交換会が始まりました。
自分も先ほど買ったお菓子を渡し、「毒入りです!」とニコニコしながら渡していると、誰もが口をそろえてこう言います。
AGCのA問題であったよね、懐かしい…」
自分も同じことは思っていましたが、全員で意見が一致するのは、異常集団としか思えませんでした。

コンテスト直前、家から持ってきたリゼロコラボの紫色のボールペンをsuzuken君に見せて自慢していました。反応は暖簾に腕押しでした。
勝負ボールペンの準備も万端なので、国内予選は通過間違いなし!

コンテスト本番

コンテストが始まります。
…問題が見えません。
この流れは去年もやっていたので、特に焦りはありませんでした。
しばらくすると問題が見えたので、bayashiko君はA、suzuken君がB、僕はCを読みました。
C問題は、構文解析ということがわかりました。が、散歩の疲れか、問題文が頭に入ってきません。しばらくぽけーっとして読んでいるフリをしていました。
その間にA,Bが読み終わったらしく、流石に自分も足を引っ張るわけにはいかないので、Cを真面目に読み終えました。
読み終えた感想は「なにこれ?」です。明らかにおかしい難易度の予感がしたので、先にD問題へ移行しました。
D問題もよくわかんないなーと思い、適当に二人に声をかけます。二人とも実装を始めているらしく、僕はC問題に戻りました。

C問題は、数式が木で表現されており、その木をうまくパズルすることで、スコアを最大化する、というものです。
とりあえず、パターンがどうなっているか、手元でこねくり回すことにしました。
が、一行に解法が見えてきません。しばらくは何もわからず、うんうん唸っていました。
すると、突然「やばい…やばい…」という声が聞こえてきました。どうやらbayashiko君のようです。声をかけると、A問題で炎上しているようです。直後、「こっちもやばいです」という声が聞こえてきました。B問題も炎上しているようです。終わった…

とはならず、今日の僕はとても冷静でした。散歩で疲れていただけかもしれません。こういうパターンの場合、3人全員が焦り始めると、誰も消火活動ができないので、自分は一つ一つ解決することにしました。

A問題をまず解決することにしました。bayashiko君に聞くと、コードは書けているのですが何故か実行がうまくいかない、とのこと。問題概要を一度聞きましたが、まぁAだし考察が間違っていることはなさそうだったので、あと10分くらい様子を見よう、ということにしました。bayashiko君はすごく謝っていましたが、僕は問題無い、とニコニコしながら対応していました。結果、suzuken君の対応をしている間に無事に通すことができました。入力ファイルにケースをコピペした後保存し忘れていたらしいです。
このようなミスは誰もが一度はすることですし、アジア通過がかかっているA問題は、確実に・素早く通すことを要求されるため、実は下手なB~D問題より難しい可能性もあります。自分もAを担当していた時はとても緊張していたため、bayashiko君が焦っていたのはとても共感できました。ここで変なイメージを付け、そのままずるずる行く方がマズいので、一旦自力でなんとか通しきる、ということができたのはかなり大きい出来事だったと思います。この世の終わり、といったような死にそうな顔をしていたbayashiko君は、なんとかC問題へと押し付けられ移動していきました。


さて、B問題はというと、考察で少し詰まっているようでした。
問題を教えてもらい、適当に自分の思考フローを垂れ流していると、suzuken君にかけそうな雰囲気が出てきたので、実装してもらうことになりました。しばらくすると、そのまま通り、無事2完することができました。
2完はしましたが、もちろんこのままで終わるわけにはいきません。
C問題は明らかにやばい雰囲気があるので、一度順位表をきちんと確認することにしました。
すると、D問題は数チームが通しているのに対し、Cは誰も通していませんでした。
おとなしく、D問題へいくことにしました。

C問題はbayashiko君にそのまま突破口を見つけてもらい、Dを僕とsuzuken君で片づけることにしました。
D問題は、風船を配る回数を最大化する問題です。
自分は、この問題を思い出していました。
b_{i}で馬鹿でかいものが2つあると、上記の問題に帰着できるよね~、というと、suzuken君は頷きました。
そのあたりで、3分割をするのかな?という発想が出てきました(馬鹿でかいb_{i}があるとき、その2つはそれぞれ1つで1グループ、残り全部を最後の1グループとするあたりから発想が出ていたと思います)。すると、ポールを3つのグループに分けた結果、そのグループの最小値が操作回数となるような並び替えの仕方が必ず構築できることを証明できました。
この内容をsuzuken君に伝え、実装をしてもらおうかなと思っていたのですが、実装方法が伝わりませんでした。ので、自分が実装することにしました。
実装はとても軽く、そのままACすることができました。
終わってから話をしたところ、suzuken君はそもそも問題を誤読していたらしいです。通りで話がかみ合わないわけでした。

さて、ここまででA,B,Dの3完です。もちろんこのままで予選が通過できるほど甘いとは思っていません。僕がD問題を通してる間に、2人がC問題を整理してくれているようでした。そこで、実装が比較的得意な僕とsuzuken君はC問題へ行き、その間にbayashiko君はE問題でエスパーを狙う、という方針を立てました。
どうやら、+-が書かれた頂点は全て根になり得るらしく、また、頂点ごとに繋がっている辺は切れたり加わったりすることはありません。なので、あとはminmaxでDPをした後、全方位木DPをすればよい、ということになりました。
構文解析パートをsuzuken君にお願いしようという話もありましたが、お互いの実装をすり合わせるのが難しそう、ということになり、自分が実装をすることになりました。
実装中、「マジ?」「助けて~」「こんなのおかしいよ~」「ほんとに?」といった独り言を無限につぶやいていました。うるさくてごめん。
実装を完了すると、149行の壮大なコードができあがりました。
コンパイルをすると…なんと通ります。サンプルを試すと…なんと合います。
suzuken君に出していい?と聞くと、OKが返ってきたので出します。
すると…ACしました。バグ無しで通せたのは、我ながら天才だと思いました。褒めてくれる方、募集中です。

僕「やっぱりおかCよ…」
bayashiko君「ダジャレですか?」
僕「し~っ!」


4完して順位表を見てみると、ぽつぽつE問題が通されていました。
Eに取り組んでいた2人に話を聞くと、考察が終わってあとは実装するだけ、という状況らしいです。4完でも通過できるかなー、とは思っていたのですが、確実に突破をしたいので、真面目に取り組むことにしました。
コードはある程度できていましたが、かなり複雑で、デバッグ役として自分が参戦するのは難しい状況でした。そのため、スペアとして、1から実装を行うことにしました。
そして、3人で同時並行で実装する時間が始まりました。

ACしたのは、bayashiko君でした。
bayashiko君はダイクストラ法をライブラリとして持っているため、ソラで書くことができないと聞いていました。
聞いていた情報と違うんですけど!!(歓喜)
bayashiko君がテストケースを通すとき、明らかに手がプルプル震えているのが見えました。緊張するの、わかります。

5完すると、なんと20位以内に自分のチームの名前が書いてありました。
この後、3人とも問題文が頭に入ってこない、と言い訳しながら感想戦をしていました。
UHISHIROを始めとする他のチームが5完すれば3チーム出場できる可能性もあったので、ひたすら祈り続けていました。

コンテスト結果

5完で、16位になりました!考え得る最高レベルの結果をたたき出すことができたと思います。早稲田の学内では2位だったので、その点のみ悔しいです。 f:id:emtubasa:20211106013618p:plain

コンテスト後

ラーメンを食べに行きました。自分が高校の頃から通っている、一番好きなラーメン屋です。

高田馬場 焼麺 劔(つるぎ) | オフィシャルサイト

f:id:emtubasa:20211106014235p:plain


帰り道、1時間電車で浮かれていました。
同期が集まっているdiscordで聞き専になりながら通話に入っていたのですが、眠くなったので落ちる、といい落ちました。
しかし、気づいたら順位表を眺めており、1時間ニヤニヤし続けました。はたから見たら変な人だったと思います。

家に着き、カバンの中身を整理していると、大事なものが見当たりません。
なんと、リゼロコラボの勝負ボールペンを部屋に忘れていました。
エミリアたん…

思ったこと(おわりに)

正直なところ、自分の競技プログラミングに対するモチベーションは万全と言える状態ではありませんでした。去年、予想外の大敗をして、立ち直るのに時間がかかりました(表面上は元気そうに振舞っていた気がしますが)。自分の周りには、かつて一緒に競技プログラミングに取り組んでいた同期がたくさんいました。しかし、今もまだ続けている人は自分一人です。後輩がたくさん頑張っているのを目にしていましたが、どうしても、競技プログラミングに力を入れられない自分がいました。
今年の6月になって、suzuken君とbayashiko君にチームを組んでもらうことを快諾してもらいました。その直後あたりは、少しだけ精進をしていた気がします。
当初、ライバルチームのメンバーを含めたAOJ-ICPCのランキングでは、自分がダントツTopになっていました。しかし、最終的には、自分はTop争いのレースからかけ離れた位置にいました。
また、自分は一時期競プロにおける自信を失っていました。9月のABCでは水パフォ相当の順位、さらにはARCで0完をし、レートを100失いました。

それでも、チームメイトは一緒に練習をしてくれていました。
加えて、同期の多くが、応援し続けてくれていました。時には僕のブログをネタにされたり、冷やかしを受けている日もありましたが、なんだかんだでAtCoderの順位表を見てくれていたり、最近の調子を聞いてくれたり、激励の言葉を添えてくれたりしていました。
本番中、チームメンバーがピンチな状況になった中でも、自分が常に冷静でいられて、最高のパフォーマンスを発揮できたのは、こうしたまわりの支えがあったからこそだと思います。
また、早稲田の競プロdiscordでは、2018年度で世界大会に通過した、yamadさん、imulanさん、ryoissyさんが通話で応援してくださっていました。コンテスト後、まずここへ報告しに行き、お祝いしてもらったのはとても嬉しかったです。今回、かなりいい順位が取れたので、少しでもこの先輩方に近づけたのかなと思っています。少しでもアジア予選でいい順位を取れて、あわよくば世界大会に…今の実力のままでいけるのでしょうか?

同期とdiscordで通話しながら今こうしてブログを書いていますが、改めて通過できたのだと思うと、今にも泣きだしそうになってしまいます。泣いたら確実に笑われるので、絶対に声は出しませんし、直接応援ありがとうとも恥ずかしくて言えないです(実は応援してませんって日にはこの世の終わりが来ます)。今後も応援してくれたら嬉しいです。頑張ります。

改めて、(まだ正確には確定していませんが)アジア予選に通過できて、本当に良かったと思います。2019年、アジア予選でも大敗しているので、その借りを返しに行かなければなりません。まだまだできることはあるので引き続き頑張って行こうと思います。

ここまで読んでいただき、ありがとうございました。

AOJ 1637 色の切り替え

問題
提出コード
解説見たらやっていることが少し違ったのでメモしておきます。

まず、同じ頂点のボタンを2回押すと元に戻るので、それぞれのボタンについては"押す"か、"押さない"かの2通りだけ考えれば良いです。
そして、全ての頂点を1度押すことを考えます。すると、全ての辺について、色が変わる回数は2回になります(辺に繋がっている頂点が2個なので)。
つまり、ある頂点集合Sについて考えると、その補集合を押した時と結果は同じになります。このことから、頂点1を押す、として最適解を探した時も頂点1を押さない、とした時も結果は同じです。
よって、頂点1は押さない、と確定させることができます。
今回作りたいのは全域木です。頂点1と頂点yを繋ぐ、としましょう。
頂点1については押さないことが確定しているので、(1,y)の辺が赤になるよう、頂点yで調整をする必要があります。この時点で、yの押す/押さないが確定します。
1,y以外の頂点xについて見てみると、

  • xを押す/押さないで、頂点1/yのどちらと繋がっているかが切り替わる

  • xを押す/押さないで、頂点1,yの両方と繋がっている/繋がっていないが切り替わる

の2パターンに分かれます。後者については、繋がっているを選択すると、1-x-y-1の閉路ができるので、繋がっていないを選択するしかありません。よって、このパターンについては操作が一意に決まります。
前者のパターンの頂点集合をA = \{a,b,c,\ldots\}としましょう。
aについて、押す/押さないを決めてみます。すると、b,c,\ldotsのそれぞれについて、aと繋がっている辺が赤くなるパターンと、黒くなるパターンが、押す/押さないで決まります。赤いパターンを選択してしまうと、頂点1,yを含んだ閉路が必ずできてしまうので、黒くなるパターンを選択するしかありません。
ここまでで、全ての頂点の押す/押さないが確定しました(Aが空の場合もありますが、そのときは空とわかった時点で、全ての頂点の押す/押さないが確定しています)。
あとは、押した結果グラフが全域木になっているか確認してペナルティを計算すれば良いです。
yを決めるのでO(N)Aについて押す/押さないを確認するのでO(N)、押す操作を実際に行うのでO(N)で、結局O(N^{3})です。
チェックするパートについても、全ての辺を愚直に走査すれば良いです。たかだかO(N)回しかチェックしないので、こちらもO(N^{3})になります。

感想

昔見た時は全く歯が立ちませんでしたが、今解いたら順調に考察が進んだので面白かったです。
昔一度解説を見て感動した記憶がありますが、全然違う考察ルートを辿ったので、記憶に残っていないことがバレました。

ICPC2021模擬国内 参加記

公式link
suzuken君と、bayashiko君とチーム"MSB"で出場しました。
ブログを書くのが久々で緊張しています。

day 0

ポケモンユナイトにハマりました。同じICPCに別のチームで出ているすず君と毎晩のようにプレイしており、一時期は5000位くらいでした。
今はレート1409で7000位くらいです。
8~9月はAOJ-ICPCを埋めて、精進メモを毎週書いていたのですが、突如モチベがぷつりと切れてしまい、後輩にばかすか抜かれました。残念。

本番

初手はばやしこくんがA、すずけんくんがB、僕がCを読みました。
僕がCを読んで†実装問題†だとわかった瞬間、一昨年の国内予選本番で実装をバグらせた記憶が蘇りました。これは誰かに実装を押し付けるしかない!と思い、すぐさまDを読みました。
Dもパッと見でわからず(2乗なら通るのになぁ~って言ってました、はやく書けばよかったです)、すずけんくんにBのヘルプを求められたので、考察の手伝いをしました。
そうこうしている間にばやしこくんがAを通しました。


ばやしこくんの手が空いたので、すかさずCを押し付けます。ばやしこくんは実装系が一番苦手ですが、ここはやむなし。心を鬼にして譲ります。
僕はEを読み、ぱっと見でわからなかったため、Dへ戻りました。その間に、Bが通りました。


しばらくしてCも通ります。D問題を僕とすずけん君で考え、2乗が通るじゃん、という話になったため、僕が実装を開始します。
すると、数分後、ばやしこ君がこう言いました。
「Eのサンプルあったので投げます」
何かの言い間違いだろうと思い、笑ってごまかしました。念のため、
「どういう解法なの?」
と聞きます。すると、
「転倒数とLIS組み合わせたらサンプル合いました」
と言います。どうやら本当らしいです。
さすがに嘘でしょ、とゲラゲラ笑いながらDを実装していましたが、数分後、
「一つ目のケース通りました」
と言われました。もう何も信用できなくなりました。
結局、僕がDを通すより20分もはやく、Eが通りました。わけがわかりません。


僕が盛大にバグらせてひいひい言いながらDを通した後、3人でFとGを交互に考えます。僕はFをほとんど考えずGに突っ込んでいました(大失敗)。
すずけんくんがFでとりあえず適当なDPを書くと言っていたので投げました。
実装が終わるも、WAが出ます。
さすがに僕もFを考えよう、と思い、10秒くらい見つめると、なんと解法がすぐに降りてきて叫びました。

「これ、区間DPじゃん!w」

嘘でした。
3分間くらい、チームメイトからすごい、天才、さすがです、とすごく褒められていたので申し訳ない気持ちになりました。
冷静になり考え直して、しっかり正しい解法を出しました。
すずけん君に伝えた後、僕も暇なので、昨年の国内予選優勝チームを真似て、どちらがはやくACできるか勝負することにしました。

負けました。


この時点で2時間たっていました。まだ1時間ありますが、G問題が不可能にしか見えなかったため、Fのデバッグをずっとしていました(1行変えれば通りました)。
その後は、三人で一生感想戦をしたり、Dの線形解を考えたりしていました。
今回はばやしこくんの大活躍のおかげでライバルチームに圧勝したかな、と思っていましたが、結局皆完数で並びました。 他のチームは完全体でないチームもあったため、かなり驚きました。

結果

15位でした。コンテスト中は16位と書いてありましたが、なぜかあがっています。
f:id:emtubasa:20211024232958p:plain

おわり

去年、模擬国内で16位を取ってから予選に落ちました。
今年は、昨年のチームメイトであるるぎうさん、とまとさんがコーチをしてくださっています。直々に頑張ってとも言われたので、今年はきちんと国内予選を勝ち抜きたいと思います。
頑張ります。

p.s. 本番で大学へ行く予定なので、ラーメンを食べるのが楽しみです。

精進メモ 2021/10/04~

書き忘れてました。

MojaCoder Random Xor Division

リンク
O(N^{2})が想定っぽい?ですが、O(N \log A_{i})で解けました。
ビットごとに見ます。すると、累積和の偶奇で右端を固定したときの相方の候補が出せます。
数日前のABC-E問題同様、2の冪乗の累積和を計算して、右端より右側で自由に切れる部分、左端より左側で自由に切れる部分のパターン数が計算できます。
あとは、ビットごとに上記を計算していき、総和を取って、全体のパターン数である2^{N-1}で割れば答えです。

ABC222

C - Swiss-System Tournament

毎回愚直に対戦させ、勝利数を計算してからソートしなおしていけばOKです。

D - Between Two Arrays

DPをいもすで高速化します。

E - Red and Blue Tree

辺ごとに通る回数をメモしてから、差が問題の条件を満たすようDPすればOKです。一回も通らないものは素直に2倍していきます。

F - Expensive Expense

全方位木DPです。
dp[v] = vを根とする部分木で、vからどこかへ観光しに行ったときにかかるコストの最大値、として計算します。

G - 222

離散対数問題のライブラリがバグっていてコンテスト中に通せませんでした。
漸化式の解き方をググって解くと、a_{i} = \frac{2}{9}(10^{i} - 1)という式が出てきます。
これがKの倍数になれば良いです。
少し変形すると、
2 \times 10^{i} \equiv 2 \mod{9K}
となります。
あとはこれを満たす最小のiを求めればOKです。

精進メモ 2021/09/27~

気温の変化にやられて一日中鼻かんでます。

AOJ-ICPC

2169 Colored Octahedra

素直に全探索します。
next_permutationで全列挙し、ひたすら回転させました。

2249 Road Construction

ダイクストラをしてから、近い順に最小全域木を計算していきます。

2178 Futon

隣接するマスを同一視して、二部グラフ判定します。
実装に少し困りました。

2302 On or Off

それぞれのマスで通る時刻はわかっているので、マスごとに計算すればよいです。
dp[i][j] = i回目に通った後、電気がオンになっている/オフになっている(j)ようなスイッチの切り替え方における最小コスト
と定義して計算していけばよいです。

2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)

チーム練です。

D. Cycle String?

出てくる回数が最大のものがn以下であれば、適当にソートして出力でOKです。
そうでない場合、s_{n}s_{2n}に最大のもの以外を置き、あとは前から回数最大のものを順に詰めていきます。
最大のもの以外が3個以上あるか、種類が3種類以上であれば問題の条件を満たします。
そうでない場合は構築できません。

E. Life Transfer

BITを7本くらい用意してごり押しました。
年齢の降順にソートして、車、バイク、乗客、の順で選んでいきます。
車を運転する人の人数を全探索していけばよいです。

F. Game on a Tree

ずるしました。
昔かっつくんが解いた時のツイートを皆で思い出してしまいました…
移動できる頂点に辺を張り直し、完全マッチングが存在すれば後手の勝ちです。
適当にDFSをして、葉から貪欲にマッチングさせて頂点があまるかチェックすればおしまいです。

ABC221

可もなく不可もなく。

C - Select Mul

2回誤読してコードを書きなおしました。
ビット全探索して降順ソートです。
leading zeroは無視してOKです(どちらにしろ答えが0になるので正しい答えが出ます)。

D - Online games

イベントソートして日付ごとに処理をしました。

E - LEQ

得意分野なので自分の体感難易度とまわりがズレていました。
数列の最初と最後を決めると、間の要素を任意に選ぶか選ばないか、になります。2の冪乗です。
i,jを決め打ったときの選び方は、累積積のようにしてO(1)で計算できます。
あとはBITで累積積をまとめて計算すればいいです。

F - Diameter set

直径の偶奇で場合分けをしました。
奇数距離の場合は、中心が2頂点に分かれます。それぞれの中心で木をわけたとき、それぞれで直径として選べる端点が計算できますが、2つの木のそれぞれから1つずつ選ぶしか方法がありません。
よって、それぞれの木の候補の数の積が答えです。
偶数距離の場合は、中心が1つになります。中心と隣接している頂点との辺で木を複数に分けたとき、先ほどと同様に直径として選ぶ候補がそれぞれの部分木で数えられます。それぞれの部分木から最大で1つ(0でもよい)頂点を選べるので、(個数 + 1)の漱石を計算します。
ここから、一つも選ばれないパターンと、一つだけ選ばれるパターンが条件を満たさないので引けば答えです。