HTTF2023予選　参加記

はじめに

今年のユースボーダーが去年の倍くらい厳しくなりそうで戦慄しています

最終的な解法

\epsilon = 0 のとき

グラフが頂点シャッフルのみされた後返ってくるため、シャッフルしても判別できるようなグラフが m 種類以上ある n のうち最小のものを探せばいいです。
これは bit 全探索と順列全探索を組み合わせれば実装できます。

\epsilon \neq 0 のとき

6 \times m 個くらいのグラフを作成し、それぞれについて各頂点における次数を昇順ソートした配列を用意しておきます。各グラフ対について次数の誤差(？)二乗和を計算し、その値が n,\ \epsilon により定まる基準以下であれば基準との差の二乗を、基準と比べ圧倒的に小さければさらに大きなペナルティを加算し、この値が最小になるようなグラフ集合を山登り法で求めます。
グラフ集合は、
1. スターグラフ
2. 次数が全て同じグラフ
3. 次数が n-1 である頂点が k 個、それ以外は次数 k であるグラフ
4. 全ての辺の生成確率をランダムにしたグラフ
から成ります。

また、グラフ作成時に、ジャッジ処理後のグラフの次数がどのように変化するかという確率分布を二項分布を用いて計算しておきます。二項分布は、はじめに前計算しておきます。
クエリ処理は、先ほど計算しておいた確率分布からおおよその作成確率を求め、それが最も大きいものを解とします。確率が 0.05% 以下のものが含まれている場合はペナルティを与えています。

最終提出

実装がまあまあ汚くなってるのは許してください

atcoder.jp

日記

day1,2 (11/11,12)

計算量の情報的に頂点関係を含めて復元するのは難しそう→次数だけで判断できる方法が欲しい
スターグラフいっぱい作ると上手くいきそう 次数から構築可能か判定するのはエルデシュガライの定理とかいうのを使って O(n)
二項分布をいい感じにいじれるといい感じになりそう とりあえず \epsilon = 0 のときを実装して 300M 点

day3 (11/13)

m<=50 は何とかなりそう
期待値との誤差二乗和を求めると上手くいきそう → 384M 点

day4 (11/14)

スターグラフに加えて次数が N-1 の頂点を増やしていく作戦→eが小さければ効果大(444M)
ε<=0.1 くらいなら 1e7 点くらい取れるようになってきてる
二項分布を前計算して更に正確な評価ができるようにした
改善してたら意味の分からないバグを踏んだ(終わった後も未だに原因が分かっていない)

day6 (11/16)

生成時に隣接させてたものと間違えることが多い(それはそう)
判定方法を改善するとかなり伸びそう
生成時に辺の生成確率を一定にしたものを混ぜてグラフ集合を山登りで決定 → 481M
次数の生成確率から復元 → 561M

day7 (11/17)

復元時の山登りは隣接交換のが良さそう→微増
グラフを決めた頂点集合の確率の積で評価→602M
頂点集合の作成をちょっと改善→797M

day9 (11/19)

次数を昇順ソートした配列の誤差二乗和をもとに評価する→Nとεに依存した評価→927M(やばい)
ε=0.33 くらいまでまともな解を出してくれるようになる

day10 (11/20)

11/17 の解が一部ケースで現状解に勝ってたので適用範囲を自力にぶたんで適用→ 1050M くらい

おわりに

上位陣の解を見ていると近いようで遠い感じがしますね。悔しいです。
認知している 18 歳以下内での順位が 10 位周辺(たぶん)なので、システスでハマることを祈っておきます。

追記


無事本選出場です！
期末初日→途中参加→翌日JOI2次→翌々日期末2日目 とかいうムーブになりそうですが何とかします

ABC268_G : Random Student ID を(ほぼ)ソートだけで解く

問題概要など

atcoder.jp

　ここでは、新入生 i の学籍番号の期待値は、 S_j が S_i の接頭辞であるような文字列の数を A_i, S_i が S_j の接頭辞であるような文字列の数を B_i としたときに(ただし、 A_i にのみ S_i を含む)、 \frac{A_i - B_i + N}{2} を計算することで求めることができることを前提とします。詳しくは公式解説をご覧ください。

atcoder.jp

解法

  1. 各文字列 S_i について、末尾に | を付け足した文字列を S_i' とします。
  2. S_i と S_i' を同じ配列に入れ、昇順ソートします。ソート後の S_i の index を idx_i, S_i' の index を idx_i' とします。
  3. A_i = idx_i 以前に現れた 末尾が | でない文字列の数 - 末尾が | である文字列の数 です。
    また、 B_i = \frac{idx_i' - idx_i - 1}{2} です。
  4. 各 A_i, B_i は、ソート後の配列を前から順に見ていくことで O(N) で求めることができます。よって配列のソートと合わせて期待値を O(N\ log\ N) で求めることができ、これは十分高速です。

解説

　簡単な例で見ていきましょう。

　 N=6
　 S=( a,\ ab,\ ac,\ abc,\ b,\ bc )

とします。このとき、各 S_i について、末尾に | を付け足したものの配列を S' とすると、

　 S'=(a|,\ ab|,\ ac|,\ abc|,\ b|,\ bc|)

となります。よって、これらを合体させてソートした配列 T は、

　 T=(a,\ ab,\ abc,\ abc|,\ ab|,\ ac,\ ac|,\ a|,\ b,\ bc,\ bc|,\ b|)

となります。
　分かりやすくするため、この配列 T の要素を順に縦に並べます。

　 a
　 ab
　 abc
　 abc|
　 ab|
　 ac
　 ac|
　 a|
　 b
　 bc
　 bc|
　 b|

　これを見ると、どの S_i と S_i' の間にも S_i が接頭辞であるような文字列のみが過不足なく存在している ということが成り立つと推測できます。例えば、 ab と ab| の間には、 ab が接頭辞である abc と abc| があり、 ac と ac| の間には、 ac が接頭辞であるような文字列は存在していないため何もありません。
　また、このことを逆手に取ると、 S_i の接頭辞である文字列の数は、 idx_j \leqq idx_i \lt idx_j' であるような j の数と等しい ということも分かります。例えば、 abc を挟むように存在している文字列は a,\ a| と ab,\ ab| の 2 つであるため、この 2 つが S のうち abc の接頭辞である文字列であることが分かります。

　では、何故このことが成り立つのでしょうか？

　ここで重要になのが、| という文字の ASCII コードは 124 である、ということです。z の ASCII コードは 122 であるため、ソートしたときに如何なる英小文字よりも後ろに来る ということが分かります。
　このことから、ソートしたときに S_i より後かつ S_i' より前に来る文字列 S_j は、「 |S_i| 文字目まで S_i と一致しており、 |S_i| \lt |S_j| である」という条件を満たしている必要があります。すなわち、 S_i は、この条件を満たすような S_j の接頭辞である ということが成立します。

　以上の議論により、この方法で S_j が S_i の接頭辞であるような文字列の数 A_i, S_i が S_j の接頭辞であるような文字列の数 B_i を求めることができると分かりました。

　余談ですが、この性質から、 S_i を開き括弧、 S_i' を閉じ括弧に置き換えて作成した括弧列は正しい括弧列であり、対応する括弧は必ず S_i と S_i' の関係になっています。
　先程の例で試すと ((())())(()) となることからも分かるかと思います。(この性質から何かしらの問題が生えるかもしれませんね)

実装例 (PyPy3, 798ms)

n = int(input())
t = []
mod = 998244353
cnt = 0
a = [0] * n
b = [0] * n
idx = [0] * n

for i in range(n):
    s = input()
    t.append([s, i])
    t.append([s + "|", i])
t.sort(key = lambda x: x[0])

for i in range(len(t)):
    if t[i][0][-1] != "|":
        cnt += 1
        idx[t[i][1]] = i
        a[t[i][1]] = cnt
    else:
        cnt -= 1
        b[t[i][1]] = (i - idx[t[i][1]] - 1) // 2

for i in range(n):
    ans = (a[i] - b[i] + n) * pow(2, mod-2, mod) % mod
    print(ans)

atcoder.jp

SuperCon 2022 参加記

はじめに

　チーム「sns」で SuperCon 本選に出場しました！今年で 2 回目です。

予選

　厳密解があっさり出てびっくり

本選

問題概要

1000頂点2000辺の有向グラフがあるよ (実際はオートマトン)
各頂点からランダムな頂点へ2本辺が生えてるよ
それぞれ a と b というラベルが付いてるよ
頂点には 0 と 1 が書き込まれてるよ

a と b からなる 500 字くらいの文字列が 2000 個あるよ
これらを適当な頂点からラベルに沿って移動させ、最終的に到達した頂点に書かれていた数字を記録していくよ
開始した頂点と記録された数字の組み合わせで文字列を区別するよ

1000 頂点全てをスタートに選んだときと同じように文字列を区別することができるような頂点の組み合わせのうち、なるべく選んだ頂点の数が少なくなる & 頂点番号の和が小さくなるようなものを答えてね

かな～～り分かりづらいため「1000桁の2進数が2000個あるよ！1000桁のうち何桁かを、選んだ結果元の種類数と等しくなるように選んでね！」というような問題だと思ってもらえれば良いです。

変数名

一々言葉で説明するのも分かりづらいため各変数を以下のように定義します。(括弧内は制約です)
n : 頂点数 ( n=1000)
m : 文字列数 ( m=2000)
w : 文字列長の平均 ( w=500)
k : 解として出力した頂点の数 ( 1\leqq k \leqq n)
loop : 1 回の山登りで近傍をとるおおまかな回数 ( loop=2000)

最終的にやったこと

  • 60 秒間 48 並列で大量に山登りをしよう！
  • 条件の判定がネック ( O(km^{2})) だから Zobrist Hash と hash set を使って高速化しよう！

　通称「下手な鉄砲も数撃ちゃ当たる」作戦です。
　この解法では (たぶん) 一回山登りをするときの計算量が O(loop(n+m\ log\ m)) になるのですが、富岳パワー & 並列化パワーで概算で 10000 回ほど山登りをすることができていました。すごい
　また前計算の計算量は O(nmw) と激重でしたが、こちらは OpenMP の力で 0.15 秒程で終わっていました。

本選中にやっていたこと

開会式(1日目)

　8:30 に起床
　前日？寝たのが午前 3 時とかだったため眠気に襲われながら開会式に参加しました。(実際後半 1 時間くらいの記憶がありません)
　参加者一覧を見ていると、チューターに去年同じチームで本選に参加した mencotton さんがいてびっくり。

　問題のテーマはオートマトンを使った文字列の分類だと判明。
　去年は感染症の疑似モデルを使った実験のような問題だったため、急に抽象的な話題になったなと思うなどしました。
　この時点で条件判定パートの計算量が [tex: O(m2)] なのはまずいという話になり、hash を使った準線形の判定を実装することを決定。

1日目

　サンプルコードを参考にやりたいことの実装 (hash による判定、焼きなまし) をほとんど進めました。
　いい感じの解が出てくることを期待し、富岳で動かしてみるとジャッジに「出力が条件を満たしてないで」と怒られてしまいます。
　結局この日はこれの原因が分からずに時間が来てしまいました。

　夜は富岳を使うことができないため、Python を使ってスコアの挙動を調べたりしていました。

2日目

　前日のバグの原因が「全ての入出力例について全ての文字列を区別することができる」と勘違いしていたためだと判明します。
　これを直し投げますが、まだ通りません。
　その後、バグの原因のうちのひとつが「2進数 mod 2^{61}-1 を hash として使っていたから」だと判明します。何で衝突しないと思った？？？

　↓ちなみにこれはまだそのバグに気付いていないときの発言です。

これはなんですか

　しかし、それでもまだ条件を満たしている解が出力されません。
　2日目はほぼ何も解決しないまま過ぎて行ってしまいました。

3日目

　この日も午前中はバグと格闘していましたが...

　午後1時頃、Zobrist Hash と hash set を採用することで、やっと全てのケースで条件を満たすような解の出力に成功します。
　その後はこれをベースに改良を進めていき、最終的に平均で k=58 くらいの解を出力できるようにしました。

4日目

　探索パートの試行回数をもっと増やせないか？という話になり、OpenMP による並列化の実装に取り掛かります。
　普段並列化なんて実装しないためバグの量がとんでもなく、最終的に正常に動くコードが完成したのは 12:24, 提出期限の 30 分程前でした。
　並列化した結果、上手くいけば k=49 くらい、悪くても k=60 くらい、平均 k=55 くらいの解を出力するようになりました。

　ただ期限ぎりぎりまで動かなかったコードですので、審査時に上手く動くかどうかはかなり心配でした。

5日目

　結果発表～～～～～！！！！！(120db)

　閉会式にて実装時の工夫などを喋った後、遂に結果発表の時間がやってきました。

　結果は......

　公開ダメらしいので伏せます(入賞は逃しました)

おわりに

　普段 Python をメインで使っていることもあってか、かなり実装スピードが落ちてしまった印象がありました。
　来年は参加できるかどうかかなり怪しいですが、もし参加できたらリベンジしたいですね。

パ研合宿2021　参加記

はじめに

パソコン力を高めるの会主催のパ研合宿2021(これ正しいのか未だに分かってない)に参加してきました！
これまではPakenとKCLCの共同運営という形を取っていたため、KCLC内募集で参加できていましたが、今年は 私が運営募集に気付かなかったため KCLC部員には外部枠で申し込んでもらうことになってしまいました。すまん！
昨年度と比べイベント量が倍になり、宿泊もできたので大満足でした。実質運営長の oliver さんありがとう...
参加記ということで時系列順に色々書いていきます

2021年11月

部員から今年のパ研合宿はどうなる的な質問を貰ったのでパ研の人々のツイートを見てみたところ、議論が死んでるという旨の話があったため若干心配になりました。

2022年2月

パ研公式から外部参加者募集のツイートがされたため、そういえば運営って募集されてた？と思い Discord を漁っているとこんなものを発見しました。時すでに遅し

f:id:Anko_nasubi:20220402144231p:plain

1日目

起床に成功　やったね

南武線を使って分倍河原まで行き、そこで昼食(マック)を取ろうとしたところ、なんと昼マックは 10:30 からとのこと。仕方がないので駅周辺を散策していたら高倉塚古墳という古墳を発見したのでそこまで行ってきました。

f:id:Anko_nasubi:20220402145759j:plain
綺麗な円墳

無事昼食を取り終え北野に向かうと、おすみーくんが既に到着し待機していました。
運営陣っぽい人々が揃ったところで、その時に居た 10 人程でバスに乗りセミナーハウスへ向かいました(クソデカスーツケース×10, 軽くテロだったと思います)。
野猿峠からセミナーハウスへ向かう最中、kaage さんが「この辺の景色よく見ておいた方が良いよ」的なことを言っていました。Freedom, 一体何が起こるんだ…

UTPC

zeta7532, to_omoT222, SotaUN, nasubi24, soraie の 5 人でチーム「チーム名ver.2.0(最終版).xlsx(自動回復済み) 」を組み参加しました(深夜テンションで提案した名前が採用されてしまった...)
E,I,J,M を頑張って考察していましたが、結局通せたのは M のみでした(zeta くんの (1-q) を掛けるという発想が無ければ解けてなかった)。高難易度力が、足りない！

夕食

昨年の記憶を頼りに同部屋の AndrewK くんと NatsubiSogan くんを探し出します。人の顔、覚えられん！
ご飯美味しかったです。欲を言えばもうちょっと量が欲しかった

開会式

あのビ太郎の素材、どこにあるんだ...
私はここで運営長がぺんぎんさんだということを知りました。

講義1

E8 さんの講義を聞きました。双子スライド、情報がスッと入ってくる感じがしてすごい　あのデザイン何処で身につけたんでしょうか
同じスライドをツイートしたらしいので後日 Twitter を見たら 2000 いいね取っててびっくりしました。E8 さん、そういえば凄い人だったな... になりました

夜

スーツケース開く場所、どこ
一人人数の関係で移動していたので、端のベッドの前を使いました。これ想定何だろう
はいらが「他の部屋員みんな作業してる～」とやってきました。かわいかった

どうやら 211, もとい最悪部屋は大盛況だったらしいですね　一日くらい混ざっとけば良かったになってます

2日目

朝

無事 7:00 に起床できました　偉すぎ
朝食はバイキングでした。大体のものを一人分くらい取っていたら腹がはち切れそうになりました。普段朝食を適当に済ませているとこういうことになるんですね。

f:id:Anko_nasubi:20220402153259j:plain

Speedrun

パ研合宿1つ目の競技 Speedrun に参加しました。ABC の早解きパートは割と得意な方だったので最も自信があったのですが...

f:id:Anko_nasubi:20220402145101p:plain

J の DP を死ぬほどバグらせた上に、K で括弧列を木にしたいnaanから進展がなかったため、9 完 2500 点・全体 35 位・オンサイト内 17 位という結果に終わりました。悲しい

Freedom

Freedom, 所謂お誕生日コンテストです。コンテストの前から Writer 陣よりとてもコンテストとは思えない発言・注意事項の数々が飛び交っていましたが、蓋を開けてみるとそこには想像以上に Freedom な問題群がありました。

【オンサイト問題】マラソン問題（物理）... 一回やりました。セミナーハウス、アップダウンがすごいですね
kaAngea 2・同校angya ... 知識で解けるものしか分かりませんでした。解説で右クリックすると Google レンズで検索できることを初めて知りました。
ビンゴで遊ぼっ！... 1 ライン BINGO　講師陣が 180 取ってたので良い攻略法があるのかと思いきや正攻法でした　すごい
宿題と魔法少女 ... 小一の学習指導要領を調べたのはこれが初めてです。
絵しりとり ... インダス文明、反則です
字短ゲーム・くそなぞなぞ2022 ... 天才パズル、むずい！
コスパ ... "C コードゴルフ" で色々調べましたがたどり着かず
Simple A⋛B Problem ... 問題の本質に終了 5 分前に気付きました
スーパー猫の日 ... 17:32 に鳴り響く複数のアラーム　それアリなのか...
逆翻訳・Obsolete-ESP・奇数優位 ... 理不尽を問題にしたらこうなるんですね
Obsolete-Empty ... 画像のプロパティ、典型らしいですね　すごい

お誕生日コンテスト典型 90, 待ってます

f:id:Anko_nasubi:20220403221253j:plain
帰りに撮った同校 Angya の 1 問　伏線回収

講義2

noimi さんによる彩色多項式の講義でした。彩色数の話辺りまではついていけていましたが、NBC が出てきた辺りから頭が爆発してしまった...
一見非自明な変換が成立するの、理解できたらおもしろそうでした。
ゆっくり見返そうと思います。

夜

某プリンセスがコネクトしてリダイブするアニメの最終話を見てました。　いい最終回だった

3日目

朝

アラームかけてちゃんと 7:00 に起きられたのに何故か二度寝して 7:50 に起床しました。絶起したかと思い食堂に向かうとまだ参加者の半分も居ませんでした。競プロerは朝に弱い
2日目の反省を活かし、サラダの量を減らしコーンフレークを付けたところ、またまた腹がはち切れそうになりました。(腹の中で膨らむ食べ物の代名詞のようなものなので、それはそう)

f:id:Anko_nasubi:20220403200829j:plain

レク

コンテスト開始の午前九時、周りを見渡してもチームメイトがいません。Discord でメッセージを送りステータスを確認するとオフラインだったため、仕方なく1人コーディングを開始します。
レクのために用意されたオンラインジャッジ上で他チームと殴り合いました。ジャッジや対戦の即時ビジュアライズができるジャッジを 2 週間で作れるの、凄すぎ...？になりました。開発力を高めるの会

私のチームは「自機・敵機とリンゴの位置で適当な評価関数を作り、可能な手のうち最も良いものを選ぶ」という手法を取りました。改善されたことを確信して投げると反復横跳びしかしない AI が爆誕するということを 10 回ほどやらかしましたが、何とかまともに対戦できるものが完成。
最終的に全体 10/22 位 まで順位を上げることができました。
ジャッジの裏をつくことに成功したチームが優勝してたのはおもしろポイントでした。Freedom 2日目

f:id:Anko_nasubi:20220403202115p:plain
レクの順位表

そしてどうやらチームメイト含む約3名は12時前に起きたようです。良質な睡眠、大事。

講義3

3日目の講義は square さんによるランダムに関する講義でした。
競プロでランダムというと、ヒューリスティックコンテストで焼きなまし山登りエトセトラをやるとき か、アルゴでテストケースが弱いことを願って乱択を書くとき などが思いつきますが、アルゴでもまともな使い方が存在したんですね。双子節(？)もおもしろかったです。

パ研杯

遂にメインイベントです。今年も大量の部分点とマラソンがあるとのことで、楽しみにしていました。
配点が 5 分前だか 10 分前だかに公開された (1-3-5-6-7-8-8-8) ので、ある程度ムーブを固めておきました。(6 まで頑張る＆部分点取りに行く)

ここからは経過時間毎に

0:01 A問題 AC (100点)

何処かに実際の講師陣のスケジュールが存在しているかと思いましたが存在していませんでしたね。

0:04 B 問題 AC (400点)

面倒くさかったので X Y 両方試す&にぶたんで解きました。

0:15 C 問題 小課題 1 (500点)

よくあるループの検出っぽかったのでいい感じに下 m 桁を表現できるものを探すと mod 10m があったのでこれで実装。小課題 3 が賢いことできないと解けなさそうだったので、とりあえず小課題 2 まで通そうとしましたが何故か WA を貰いました。悲しい
沼りそうだったので一旦パスします。

0:32 D 問題 小課題 1 (550点)

数分考察してみましたがサッパリだったので、とりあえず自明な小課題 1 を通しました。

0:53 E 問題 WA&TLE (550点)

小課題 1 を色々乗せたセグ木上のにぶたんで解こうとしましたが、定数倍が重かった上に log の 2 乗が掛かってしまい TLE。しかも想定していない WA までついてきました。とりあえずパス。

1:04 C 問題 AC (950点)

試しに m=16 でループ長を調べてみたところ、愚直が余裕で間に合うことが分かりました(最初から実験を、しよう！)。これを実装し、見事 AC 。

1:26 D 問題 AC (1500点)

先程ちょっと考察してサッパリだったため、一手ずつ考察を進めていきました。具体的には、「十中八九 DP なので、どういう状態だったら嬉しいか・どういった配列・条件・遷移だったら正しく求められるか」を考えました。
すると、

  1. B で昇順ソート
  2. dp1[i] = (選んだ B_i の和) = i のときの、(選んだ B_i の和) - (選んだ A_i の和) の最大値 (0 <= i <= T)
    dp2[i] = (選んだ B_i の和) > T , (選んだ A_i の和) = i のときの 、(A が解いた問題数) - (B が解いた問題数) (0 <= i <= T)
    となるような、配列 dp1, dp2 を定める
  3. いい感じに遷移すると、dp2 の最大値が答え

という解法を思いつきました。
これを実装し投げると、見事 AC 。
ここまで綺麗に考察でき正解に辿り着ける問題は初めてでした。今回の問題の中で一番好きです。(運営陣によるとこの原案が出たのは数日前だったらしい　ギリギリ)

1:35 F 問題 小課題 1 (1520点)

小課題 2 以降は何も分からなかったので自明な 1 を投げました。

この後また E に粘着しますが、小課題 3 でセグ木を 4 本作る案など訳の分からないものが出てきたのでまたもやパス。

2:17 G 問題 小課題 2 (1670点)

開始 2 時間くらいまでずっと頂点を 1 度ずつ通るだと思っていました。なんで？("巡回セールスマン　補題" とかで調べたりしてました)
辺を 1 度ずつに読み換えると、小課題 2 が自明だと分かります。
Python の defaultdict を使って通しました。

2:45 G 問題 小課題 1&2 (1870点)

小課題 1 では二乗が許容されているため、各 (l, r) について O(log N) 程度で判定ができれば良いということになります。
各頂点の次数が全て偶数なら条件を満たしそうなので、hash でその時点において次数が奇数である頂点の集合を管理してみます。サンプルを試してみると 3 で落ちたのでよく見てみると、連結でないときに壊れるようです。
そこで UF で連結判定をして提出してみると、小課題 2 で 1 ケースだけ爆発しているケースがあったため、小課題毎の条件分岐を逆にして回避し通しました。

E に戻って考察していましたが、進展はなくコンテストは終了。

結果

100-300-500-600-0-20-350-0 の 1870 点で全体 28 位・オンサイト内 11 位でした。
高難易度力はそこまで自信がなかったので予想以上に取れて嬉しかったです。

f:id:Anko_nasubi:20220403214416p:plain

Deathgame

運営が Deathgame などといった迷言も生まれたこのコンテストですが、私は R2 敗退という結果でした。R2-B でロリハをバグらせたのが敗因です。悔しい～
双子が R3 唯二(？) の AC を取ってました。すごい。

夜

最終夜だしワイワイやりたい！今後あんまり出ないだろうしオンサイト SRM もやりたい！などと思っていたのですが...
寝落ちしました...(悲しい！)

4日目

朝

今日はちゃんと 7:00 に起きました。寝落ち効果
昨晩寝落ちして入れなかったので朝風呂に入りました。八王子の朝寒すぎませんか
運営は二日連続絶起したらしいですね。　お疲れ様です。
やることもないので講堂でのんびりしていました。

講義 4

tatyam さんによる木の色々の講義でした。
直径からそれ以外を垂らすっていう発想、今までしたことがありませんでした。これ使えば格段に解きやすくなる問題かなりありそう　　 それと HLD もそろそろライブラリ化しなきゃなぁ... になりました。

講義前か後か忘れましたが、tatyam さんが IOI2018 で作られた IA ちゃんのクリアファイルを配ってました。はじめ IA ちゃんのことを IOI のキャラクターか何か(JOI のビ太郎のような)だと思っていたのですが、あのボーカロイドの IA ちゃんでした。どうやら IOI2018 を日本でやった時に IA×ONE のライブがあったらしいですね。　すごい

LT大会

数学や開発やFreedomやIOIの様々な話を聞けました。よく使われる単語攻撃、賢い。
スライド無し LT をしていた人が数人いましたが、彼らみたいな話を組み立てる能力、欲しい～と思いながら聞いてました。

閉会式

パ研杯銀賞(オンサイト内 6~12 位)を頂きました。嬉しい～

f:id:Anko_nasubi:20220403220645j:plain
順位を弁えて取ったルマンド1本

この後新宿方面に遊びに行ったグループがあったらしいですが、私は体力の限界を迎え家に直行していました。翌日息絶える覚悟で遊びに行けば良かったですね。

おわりに

4 日間あっという間でした。楽しい時間は早く過ぎると言いますが、まさにその通り
来年は恐らく運営として参加すると思います。KCLC枠復活させたいし
原案も余るほど考えときます。原案の数だけ日数増えたりしないかな～

最後に...
oliver さんをはじめとした運営陣の方々ありがとうございました！！！ 楽しかったです！！

f:id:Anko_nasubi:20220403221814j:plain
さくら館前の桜

JOI 2021/2022 本選　参加記

はじめに

100-100-33-0-9 で合計 242 でした
落ちました

開始 1:30 前

今回も絶起はしませんでした　えらい！

~0:10 A 問題　AC (100点)

想定しゃくとりなんだろうけど面倒くさいからにぶたん！w

~1:00 B 問題　部分点 (164点)

二分探索なのは合ってる自信があったのでオーバーフローを疑う→なかなか治らないのでスキップ

~1:50 C 問題　部分点 (197点)

とりあえず貪欲 or bit 全探索でおしまいの 33 点分を通しました
ここから満点考えたり B のデバッグをしたりしましたが進捗なし

~2:00 E 問題　部分点 (206点)

こちらも自明部分点 9 点を獲得
小課題 2 は実装に時間がかかりそうだったので後回し

~2:20 B 問題　AC (242点)

コードとにらめっこしていたらとんでもないミスを発見して投げたら無事通りました(オーバーフロー自体は部分点のときに何とかなってた　なんで？)

~4:00 (242点)

C 問題をずっと考察してましたが、
・ 貪欲は嘘
・ DP をしたいけどいい感じの計算量になる組み合わせが分からない ( Bを昇順にすれば DP できそうとはなりましたが焦って頭が爆発してうまい遷移が思いつきませんでした...)
となったところから進展が生まれず時間切れ

おわりに

本選落ち黄コーダーになりました　さようなら
来年は 10 以下全部埋めて 450 点取ります

HTTF2022 本選　参加記

はじめに

HTTF2022 本選に出場して 39,888,259 点、全体 8 位・ユース枠 2 位を獲得しました！
ここまで取れると思っていなかったので嬉しいです！！

f:id:Anko_nasubi:20211218200543p:plain

問題概要

できるだけ短いコマンドでお掃除ロボットを動かしてね

atcoder.jp

考察

短い・操作数が多い・多くの範囲を掃除できる の 3 つを満たすようなコマンドが入っていると嬉しいので、手作業で最初に入れる用のコマンドを探していけば良いかなーと考えてました。
結果この方針が大正解でした。

最終的な解法

① 各マスから他のマスまでの最短距離を BFS で求める(このときのマス i からマス j までの最短距離を d _{i, j} とします)
② 答えに x(y(LrrF)y(RllF)) を入れる
③ 次に向かうマスを、まだ掃除をしていないマスの集合を S として、 d _{現在のマス, i} - \sqrt{(\sum_{k \in S} d _{i, k}^2)/|S|} の値が最も小さいマス i にする
④ ③の操作で移動したマスのうち、移動距離が 3 以上である場所で分割する
⑤ ④で分割してできた塊を、山登り法で移動距離の和がより小さくなるように並べ替える
⑥ ⑤での並び順に従って、なるべく F が連続するような・最短距離を通るようなコマンドを記録していく
⑦ ⑥で連続している文字をまとめる
⑧ ⑦で連続している塊をまとめ、②にくっつける
⑨ ②～⑧ の操作を、
y=2～ 9
x= \lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor -5 ～ \lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor の乱数
で行った後、最も良かった y に対し、
x= \lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor -6 ～ \lfloor 5000/(8 \times y) \rfloor - \lfloor 200/(8 \times y) \rfloor
でそれぞれもう一度②～⑧を行う
⑩ ⑨のうち最もコマンド長が短かったものを出力する

この解法に則ったコードが下のものです。(最終提出まで伸びてくれました)

atcoder.jp

f:id:Anko_nasubi:20211218212805p:plain

コンテスト中考えていたことなど

f:id:Anko_nasubi:20211218213207p:plain
AtCoder Marathon Replay さんより

0:01

とりあえず正の得点を取ろうと思い、以下のコードを投げました。

f:id:Anko_nasubi:20211218213411p:plain

Python 初心者か？？？？？

再提出はせずまともな解の実装を始めました。

~ 0:40 (36,066 点)

とりあえず「隣接するマスのうちまだ掃除されていないものがあれば移動する・なければランダムで移動する」というコードを書きました。
結果はほとんど全てのケースで掃除しきれず。
明らかに違うので別の方針で進めます。

~ 1:12 (10.06M 点)

「まだ掃除されていないマスのうち、現在のマスから最も近いものに移動する」というコードに書き換えました。要するに貪欲です。
ここで提出したところ瞬間 1 位に浮上しました。(かなりびっくり)
方針は良さそうだったのでこのコードに肉付けしていく形で実装を進めていきます。

~1:54 (10.40M 点)

上の解法の④・⑤にあたる山登り法、⑦にあたる文字数削減を実装します。
完成して提出してみると何故か点数が落ちてしまいました。
デバッグをしていたところ、現在の向きがうまく更新されていないことを発見しました。(このミスは今回何度もやりました。学習能力)

~2:31 (10.42M 点)

上の解法の⑧にあたる文字数削減を実装しましたが、(なんとなく予想はしていましたが)大きなスコア改善にはなりませんでした。

~3:06 (11.17M 点)

ここでようやく②の前身にあたる「最初に適当に埋めちゃおう作戦」を実行します。
このときの文字列は 20(3(15Flrr)) → 20(3(5Flrr))20(3(5Frll)) にしています。

~4:11 (14.29M 点)

遂に 10(30(LrrF)30(RllF)) という型を発見します。
この型で提出したところかなり伸びたので、これを少しずつ弄って伸ばしていきました。

~6:56 (18.38M 点)

上の型を一般化し、様々な乱数で最適なものを探していきました。
このとき最もスコアが出たのが、
x=14 ～ 17
y=28 ～ 37
という組み合わせでした。

~8:00 (39.88M 点)

順位表凍結直後、試しに x と y を入れ替えてみたところ、なんとスコアが倍近く伸びました。(流石に笑ってしまいました)
y が小さいほどスコアが良くなるのでは？と思い、最終的に解法にも載せた通り y=2 ～ 9 くらいが最適だろうという結果になりました。
凍結時点の順位表を見る限り他の人のスコア変動が無ければユース 2 位だったので、かなり興奮していました。

f:id:Anko_nasubi:20211218221149p:plain

上のグラフからも分かる通り、凍結後の一時間は出すたびに目に見えるスコア改善ができ非常に楽しかったです。

おわりに

初めてのマラソン大勝利でした。ヒューリスティックコンテストは戦略等はほとんど要らず(ほんとに？)、完全地力勝負なので勝てるとアルゴ以上に気持ちいいですね。マラソン堕ちしてしまうかもしれません。
最後に、このような問題・コンテスト・その他ノベルティ諸々 を用意してくださったフューチャー株式会社さん、ありがとうございました！来年も機会があれば～

JOI2022 2次予選　参加記

参加記(やっていた、考えてたことのメモ)です

7:00 (-6:00)

2次予選0問目 "起床" AC—

12:57 (-0:03)

コードエディタを開くのを忘れており慌てて開く
準備はちゃんと、しようね！

(ここから競技開始後の経過時間)

0:01 A 問題 AC (100点)

去年の A 問題のようなのを予想して身構えていたので少し拍子抜け
キュー使うと楽になるいつもの ABC-C

0:06 B 問題 AC (200点)

皆大好き BFS
こっちも 去年のパンケーキとは違って ABC-C によくありそうな問題でびっくり

~0:10 C 問題

今度こそ激ヤバ問題が来るかと思って開く
制約が微妙な数字だった上にパッとそれっぽいコードが思いつかなかったのでスキップ

0:25 D 問題 WA

問題見る→実家 DP じゃん！→二次元セグ木を持ち出す(？？？)→サンプル合わせる→WA&TLE
軽率にデータ構造で殴ろうとする悪い癖が出た

0:38 D 問題 AC (300点)

二次元セグ木なんて使わなくても適当にメモしてあげれば大丈夫だということに気付く
遷移が若干ややこしいけど diff 1400 くらいな印象

0:59 C 問題 AC (400点)

揃えたい和と縦の分割方法が定まれば横は一意に定まることに気付く

作れる和は A_i,j の和 /2 ~ /(H*W) の範囲に収まりそうだったのでその範囲で累積和を使って判定 + OK だった範囲の左端から右端に辺を張って、全体の左端から右端への道順を足せば答えだろう

という解を書くがサンプルが合わない
横の分割方法が異なるものが存在していることに気付いたので分割した場所を 2 進数で記録→同じものだけを辿ると AC

1:19 E 問題 部分点 (416点)

ひとまず自明部分点を取りに行く
小課題 1 は愚直
小課題 2 は S[u] != S[v] である辺を記録して一致するものがあるか見る

2:04 E 問題 WA

クエリ先読みして繋ぐ地域が同じものを一括で処理する方針で実装
Undo 可能 Union-Find があればできると考え持っていた Union-Find を改造する(？？？)
サンプルは合ったが提出したらボロボロ

2:22 E 問題 AC (500点)

Undo 可能 UF が無くても適宜座圧 BFS をすればいいことに気付く
実装して提出すると 3765ms (？？) で AC

結果

満点です！！やった！！

f:id:Anko_nasubi:20211212160426p:plain