以下の内容はhttps://olphe.hatenablog.com/より取得しました。

ACPC2025参加記

はじめに

ICPCのときにかっつ君と「絶対ACPC行こうな」と盛り上がる。そのとき他にも何人居たはずだがいずこに……？

day1

例によって東武鉄道や会津鉄道を乗り継ぎ会津へ。移動中一生かっつくんと過去のACPCの話をしていた。

 

途中めっちゃ雪積もっててすごかった。

一面の雪

あいづっこ宣言を見たかっつ君が「yamadを思い出す」と言っており懐かしい気持ちに。yamadの顔っぽい広告たくさんあると思っていて、情報を募集しています。

喜多方ラーメンを食べた後会津大学へ

 

コンテストは立命セット、kotatsugame, n_o_n_o_nと共にkotatsugame_marunageで参加。オンサイト2位

D ある行について着目したときに、最も近いものの集合はマスについて連続であり、かつその行には一塊しか存在しないため二分探索によってそれぞれが何個ずつ存在するかを調べられる。

E ギャグ

F 高度ごとにimos法

H |S|>|T'|の場合は、|T'|を全探索してTの後ろから貪欲法でT'を構築できるか調べられる。そうでない場合はTの後ろからRev(S)を取り出し、残った部分での最長の回文をLCSのようなDPで求める

 

kotatsugameが高難易度をバシバシしばいていて格好良かったです。終盤はn_o_n_o_nさんと考察出しながらKを考えてて楽しかった。

夕食は集団で焼き鳥や焼き豚の店に行く。日本酒の会津政宗がめちゃおいしかった。

day2

コンテストは東北大セット、かっつ、MMRZと共にthunderbirdで参加。オンサイト3位

E 文字列を1で区切った時に各区間にある0の数を持った数列に着目すると、操作1は隣接する2要素から1を引く操作に、操作2は端以外の0を一つ削除する操作に言い換えられる。数列の最大要素と総和に着目すると各操作が何回行えるかわかる。

L 1要素の追加で構築できる場合は自明に判定でき、sとtの差がでかめの奇数かでかめの4の倍数なら常に2要素追加すれば構築できる。どちらでもない場合は1要素を追加してから2要素の場合に言い換える。

 

終盤は全員解けそうな問題に取り組んでおり、誰かがもう1問解けると幸せだった……

 

kotatsugameと夕食の後、富士の湯へ、合宿参加者が割といて楽しい。

ARCはABCEを解きパフォ2800でカンスト、あまりに嬉しい……このまま橙まで復活していきたい。

ARCの後でixmelと部屋で飲酒をしていたがixmelが一瞬で寝たので一人寂しく日本酒を消費していた。

day3

朝早起きして鶴ヶ城に行く。多くの場合戊辰戦争は明治政府側の視点で書かれるが、鶴ヶ城においては会津藩視点での歴史が書かれており非常に興味深かった。見学時間は全然足りんかった……

コンテストは会津大セット、toam,ococonomy1と共にtouhokudaiで参加。オンサイト2位

B 人の配置をnext_permutationで全探索

D 行列累乗 去年一生Antimatter Dimensionsをやったいたのでうれしい気持ちに

E 包除だという主張をしていたが、toamさんによりセグ木解が提示されそのまま実装も任せた。それはそうすぎる。

G bitごとに考える。そのbitが立っている数と立っていない数を持って行列累乗

I 残す頂点を持つDPで解けるというところまでたどり着いたが、残す多角形に使える辺の条件に関する考察漏れがあり解けず……とても悲しい……落ち着いて考察を行います。

J ococoさんがある程度考察をしていたところに、ロリハで部分文字列の同一判定をすればよいと指摘をし、実装も行う。

N Nより桁が少ない数については、dp1[桁数][使用した数の種類数]=の通り数,dp2[使用した桁の集合][そのような集合を含む合法な集合のサイズ]=の通り数 を求めておくと通り数が求められる。桁数が同じで小さい場合は初めて異なる桁を全探索し、dp1,dp2を使用して通り数が求められる。Nについては条件を満たしているか調べる。

 

この日は様々な問題でチームメイトと考察を進める場面が多く、一番チーム戦してる感があった。

 

おわりに

一生擦り倒していたACPCに再び参加できて感謝の気持ちでいっぱいです。運営の皆さんありがとうございます。

HUPC2023参加記

参加記 作問

5/2

船のバスセットを予約していたので、同行者と神戸で集合しコメダで暴食した。 バスで電波の弱い兵庫の山奥を移動しながら、準備で少し問題が発生していたので指示を出していたりした。 舞鶴港でお散歩をしつつ写真を撮った。釣り人がたくさんいて興味深かった。 ここに船の写真を貼る。

5/3

ほとんど船で過ごしていた。 途中マジック見たり、日の入りを見ようとしていた。 出航から約 21 時間でようやく北海道に上陸

急いで札幌に向かい、いちご君たちと異常に元気よくイクラを注いでくれるイクラ丼を食べた。おいしょー！！！

5/4

昼は Picante に向かったがめちゃくちゃ混んでてあきらめた。 ノースコンチネントは入れんかった、悲しい……

コンテストは りあん、m_99 と組んで HUPC2023_onsite_KING で参加した。

まず A を開く、最も簡単な方から 3 問以内らしいけど全然解けないが？ よく考えると $N>2$ のときには上下判定は自由にできることがわかる。 手で $N=3$ のときを考えたあと、 $N=4$ について実験を行うと解けた、見抜けないギャグ困る……

m_99 から L や M の話を聞いていたがよくわからなかったので(は？) J を読むと Trie で解けそうなので少し考えて書く。

その後しばらくみんなで G を考えていたが諦めモードに、その後 E の話を聞いたが解けてそうだったので他に移る。 何気なく見た D が自明だったので書く。

チームとしては 11 完 3 位で良かった。 コンテスト後は懇親会で肉を食べまくった。ジンギスカンと言っていたがジンギスカンどこ行った？

5/5

今日こそ Picante に行く。運営なのにコンテストぎりぎりになってしまい反省……美味い。

クラー対応をしつつ、解説を作ったりまとめたりしていた。 考察の声が聞こえてくるの無茶苦茶楽しくてニヤニヤしてしまう。 コンテスト後には解説を行ったが、解説するの難しすぎた。

今日は少人数で居酒屋に行き、主に魚を食べた。

5/6

早い時間に根室花まるの整理券を取りに行き、なんとか入ることができた。 かなり美味くて安い、異常です。

コンテストははむへいさんと組んで HUPC_oh で参加した。 最初は B 以降を読んで、簡単そうな問題を難しそうな問題に分類した。

N がいつものすごろく系で解けそうなので、取り組む。 実装にだいぶ苦戦したが、FA だった。うれしい。

K に張り付いた上で解けなかったのかなり最悪だった。

F を誤読していて全然違う問題を解いたりしていたが、何とか帰ってこれてAC。

はむへいさんの L の考察が概ね正しそうだったので少し修正して実装を任せた。

時間も無くなってきたので簡単そうな B を解こうとする。分類したときには確率的素数判定が頭にあったが完全に忘却してて終わり。 急いで D を書いた。こちらは何とか間に合ったが、L のデバッグがぎりぎり間に合わず惜しかった。 チームとしては 4 完 38 位。

入浴したりラーメンを食べたりしていた。

5/7

帰り、ううううう

空港の搭乗ゲートの前に雪印パーラーがあってラッキー、おいしいね。

農工大セットの準備について

もともとは 2022 年度に開催される可能性もあったので、農工大セットに関わっていた。 とはいえ本格的に作業が始まったのは 2023 年度になってからだった。 んぐくんが自動テストとか導入してくれてよかった。

4/1

セット決めを行った。この段階では D がなく、また F の実装が激重だと認識できていなかったため 3 時間コンテストには問題が不足していると判断し、D 以外を確定した。D は 4/8 までのどこかで生えた。 この段階で各問題について writer (generator , validator , 解 , HTML を書く) と tester (validator , 解を書く) 2 名を決めた。

4/9

多くの問題でケース生成が終わった

ABC の読み合わせ

4/10

DEFの 読み合わせ

4/11

GHI の読み合わせ

4/16

全ての問題でケース生成が完了しほとんどのテストが終わる。

4/22~4/28

ととりとヘクトさんにテストをしてもらう。

4/27

読み合わせ

4/28~

微調整

農工大セットの各問題についての個人的所感など

A

オンサイトでの AC を保証しつつ、作問初参加者の作業慣れに使えた。

B

低難易度いじわる枠

C

OR convolution を忘れており結構苦戦した。みんな包除で解いてて悲しくなった。

D

原案をした。最初は区画の swap がなくてオンラインだったが、区画の意味がないとの指摘を受け区画 swap を追加し、オフラインにした。 苦しみながら高難易度問題生やそうとすると複雑な設定になるの何とかしたい。実装頭壊れそうだった。

E

原案をした。案は 3 年前ぐらいに出ており、当時はみんな自明みたいな感じだったがみんな忘れて高評価だったので出した。 よく考えると解説では $v_i = 1$ の場合を分けないといけなかったな。この問題は難易度評価がかなり難しかった。

F

もともと $N$ のみが与えられている状態で未解決問題として提案されていた。この状態でも解くとかなり気持ちいいタイプの問題だったが、OEIS やエスパーで解けるため非常に悲しい。 対策として出題したような問題に改題した。実装頭壊れそうだった。

G

低難易度枠 問題文間違えててすまん。

H

見た目いかつすぎない？ 開き括弧を特定する部分と、特定した後に正方行列しか与えられないことを利用すると行列の解釈が一意になるパートが結構面白い。 実装自体は簡単

I

原案をした。問題複雑ですまん & 問題文間違えててすまん。

まとめ

作問側としてようやくオンサイトで参加できてよかった。 運営を行って頂いたHCPCのみなさん、コンテスト開催の支援を行って頂いた会津大学の渡部先生に感謝します。

ICPC模擬地区予選2022参加記

参加記

模擬地区予選に参加しました。

jag-icpc.org

JAG系のオンサイトは久しぶりなので楽しみにしながらレジりました。

コンテスト前

早くから人が集まっているだろうと予想して意気揚々と開場時刻ごろに会場に向かうと参加者が誰も来ていなかったので見知ったスタッフに交流してもらっていた。 ここでチームメイトの一人と初顔合わせなどもした。

コンテスト

A:微妙につらそうにしていたので手伝いに行った。 B:知らないうちに通っていた。 D:比較的簡単そうなので考えると、普通のLISとかなり近い方法で求められることが分かったので頑張って詰めた。 H:SCCすると末尾から先頭に行ければよいので書く。 L:実装ができませんと考察が届けられたので解法を確認しつつ書く。 以下解けてない C:一般マッチングだねと言っていた。交差しないのそれはそうすぎる。 I:二人がかりで必死に嘘解法を実装していて悲しくなった。 残り:コンテスト中に解くのは無理そうだったので真剣に考えていない。

コンテスト後

予選のないオンサイトはかなり久しぶりだったので知らない顔が多かったが、CUPCの3人やharukiさんなどと新たに(？)交流ができてよかった。どうやらわざわざ呼び止めてもらったらしく感謝……

今年でICPC最後なのでJAG入りが近づいてきている。何かしら貢献できるとうれしいね。

HUPC2021day2農工大セットのコメント

作問

コンテストへのリンクです。 Aizu Online Judge Arena

A問題

簡単枠が欲しいねえって言っていたらいつの間にか生えていた。

1回で $1 \rightarrow 6$ にしている人や、$1 \rightarrow 5 \rightarrow 6$ を忘れてる人が多くてWAを出していてよかった。

B問題

G - Good Vertices

これ見てなーぶ君が思いついていた。普通に難しくない？

問題文を自然に書くのがかなり難しくて紛糾した。

C問題

これなんでたくさんペナ出てたの？

$1\le H,W \le 10^{5}$ で解けたらそうするつもりだったけど解けなかった。悲しいね。

D問題

鳩ノ巣原理、強い人でも見落として事故りがちなので出した。

さすがに明らかすぎたのか期待してたほどは事故ってなかった。

E問題

これもともと正十二面体で出そうって主張していたけどみんなにめっちゃ嫌がられたのでこうなった。(サイコロ担当さん？)

シミュレーション許す制約なの困る！(半分ぐらいシミュレーションしたので)

F問題

最初 $O(N^{3} max(b))$ とかのつもりで出していたんだけど明らかに一つNが無駄なのを指摘させてしまった。恥ずかしい。

ととりが無限に嘘解法投げてきたのでかなり嘘に強くなってそう。

G問題

これ見たとき笑っちゃった。構文自体はかなり親切(？)で行列累乗とかの高速化パートも構文解析と一緒に出てくるのが新鮮に感じた。

絶対面白いと思ったので出題をかなり主張した。

Weird LIS(AtCoder Grand Contest 055)

AtCoder

問題概要

ある $1$ から $N$ までの順列 $P$ があって、$P$ の $i$ 要素目を取り除いたときのLISの長さを $A_i$ とする。$2\leq A_{i}\leq M $ を満たすような $A$ は何通りあるか。

事実

$P$ のLISが $K$ だとすると、$A_i$ は $K$ か $K - 1$ である。また $K$ であるとき、 $i$ 番目の要素を使わないような長さ $K$ のLISが存在する。 $P$ の要素は3種類に分類できる。

・取り除くとLISの長さが短くなる要素

・取り除いてもLISの長さは変わらないが、LISに含まれることもある要素

・LISに含まれることはない要素

解法

$A$ の全ての要素が等しい場合とそうでない場合に分けて考える

全ての要素が等しい場合

以下のようにして $A_i = K \space (2\leq K\leq N/2)$ を満たす $A$ を作ることができる。

$2,1,4,3,...,2K,2K-1$

以下のようにして $A_i = N - 1$ を満たす $A$ を作ることができる。

$1,2,...,N-1,N$

全ての要素が等しい場合以外

$2\leq A_{i}$ の条件より、$2 < A_i$ を満たす要素がある。これは $P$ のLISの長さが $3$ 以上であることを意味する。 また、$A$ に異なる要素があるため、$P$ の中に取り除くとLISの長さが短くなる要素を $1$ 個以上、それ以外の要素を $1$ 個以上含む必要がある。

LISの長さが短くなる要素 $X$ 個とそうでない要素を割り振ったとき、LISの長さは $X$ 以上である。LISの長さを $X$ にしたければそうでない要素を全てLISに含まれることはない要素にすれば良いし、$X+n$ にしたければ、そうでない要素のうち左から貪欲に連続した二つをLISに含まれることもある要素にすれば重複なく数えられる。

これを数えることを考える。

以下のような遷移を行いつつ通り数を数えると良い。

①取り除くとLISの長さが短くなる要素を一つ追加する。

②取り除いてもLISの長さは変わらないが、LISに含まれることもある要素を二つ追加する。今後②と③を使用できなくするかわりに④を使用できるようにしても良い。

③LISに含まれることはない要素を一つと取り除くとLISの長さが短くなる要素をこの順番で一つずつ追加する。

④LISに含まれることはない要素を一つ追加する。

その際、以下のような情報を持っておく

・追加した要素の数

・LISの長さ

・①か③を行ったかどうか

・①以外を行ったかどうか

・④を行うことができるかどうか

提出

Submission #28318663 - AtCoder Grand Contest 055

Online MST(THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007))

AtCoder

$8$位だったのでやったことを書く。

問題

$N=400$ 頂点 $M=1995$ 辺のグラフがある。辺のコストははじめ不明である。 $ M $ 本の辺について重さの情報が与えられるので、与えられるたびにその辺をグラフに残すかどうかを選択する。与えられる辺の重さは頂点間のユークリッド距離を四捨五入した値の $1$ 倍以上 $3$ 倍以下である。 最終的にグラフが連結である必要がある。 残した辺のコストの総和を小さくしたい。
なお、グラフの辺は最小全域木$5$個の和集合である。

初動

木以外を作る意味はないので最終的には木だけが完成するようにする必要がある。 後の方の辺の重さが分からない状態である辺を使うかどうかを決めないといけないので、後の方の辺の重さを適当に決めておく必要がある。これは期待値である2倍にする場合とそれぞれランダムに決める場合があると思うが、とりあえず $2$ 倍に設定して毎回最小全域木を求めると、$13917323561$ 点($221$ 位相当)になる。実際には使う辺の倍率は $2$ 倍よりも小さいので、適当に $1.8$ 倍とかに設定して求めると $14080471444$ 点($153$ 位相当)とかになる。

辺の重さをランダムに

一律に何倍とかに決める代わりにそれぞれの辺の重みをランダムに決めてから最小全域木を求めて、辺を使う場合と使わない場合のスコアの期待値を比較する。これを時間いっぱい回すと $14136487217$ 点($59$ 位相当(強くない？))になる。辺の使用状況を見ると、最初の方の辺と最後の方の辺で使用率が異なるように見えたので、不明な辺の重さをランダムに決めたあと適当に定数を加えると調整できると考えたので、何個か試すと $2$ 加えるのがよさそうだったのでそうする。$14189655151$ 点($28$ 位相当)になる。

高速化

手元で動かすときに生成回数を増やしてみるとかなりスコアが改善されたように見えたので高速化を行うことにした。各辺について過去の採用確率を求めてみると、過去の採用確率が実際の採用確率に強く影響しているように感じたので過去の採用確率が一定以上だと強制的に採用するようにした。あと、最初の方の探索回数を犠牲にして後ろの方の探索回数を増やしたが、これは効いてるかよくわからん。ここまでで $14205289770$ 点($19$ 位相当)

スコアの差の期待値が大きくなった場合途中で採用/非採用を確定するようにするとかなり速くなる。$14224313041$ 点($8$位)

やらなかったこと

あらかじめグラフを生成しておくと、毎回辺のソートしなくてもいいらしい。

おまけ

これ、下の方はほぼ採用されるし上の方はほぼ採用されないので予想するだけ無駄みたいなのがあるのか？

ICPC2021国内予選参加記

参加記

予選以前

去年まででふぇりんさんが引退してしまったので今年からはなーぶ君が加入して新生nowcowとして生まれ変わった。

なーぶ君には幾何とフロー実装できるようにしといてくれ！と叫んでいたらAOJの幾何の基礎のやつ(？)とか埋めていてえらかった。 でぃぶ君には去年まで構文解析とかの実装をやってもらっていたので、僕もデータ構造頑張るか～って言っていた。アジアまでには頑張ります……

模擬国ではなーぶ君に全方位木DP投げてもよさそうであることが分かったので嬉しくなっていた。考察をしたいので。

国内予選

でぃぶ君A なーぶ君B おるふぇCで開く。Ｃを開くとかなり難しく&重く見えてかなり焦る。でぃぶ君がAを通してしばらくしているとBで2ペナ生えてるのが見えたのででぃぶ君にCを押し付けてBの話を聞きに行くと、かなりよくわからないことを言っているように聞こえたので、僕が書きますと言う。 書いているとペナが増えていて焦るが、4ペナで通す。途中でペナが20分であることを説明する(ごめん……)

CはやりたくないのでDとEを見るが、Dはひらめき系に見えてひらめかなかったのでEを考えると、タクシー乗る回数を少ない範囲では全探索して多い範囲では最小化すればいいことが分かるので正しいことをなーぶ君に軽く確認して実装を始める。そのころでぃぶ君はCが解けたらしく、Cの実装を始める。途中誤読に気づいたが、修正して提出するとWAが出る。なーぶ君とデバッグしていたが、何点か修正しても古い出力と変わらないのでかなり焦っていた。ここまでで2時間ぐらい経過していて140位とかで2度目の予選落ちが頭をよぎっていた。あまりにも苦しくなってきたので変わってないけど出すか！って言って出すと(？)通る。その30秒後ぐらいにでぃぶ君がCを通し、一気に20位ぐらいまで上がりお祭りになる。僕はこれで予選は通過したかな～とか言っていた。安心したので冷静さを取り戻す。

Dについて考えると最初の3要素の順番はどうでも良いことが分かり、実験をするとサンプル2は以下のような順序のみ条件を満たすことが分かる。

1 3 3 4 3 3 4 3 3
3 3 4 3 3 1 4 3 3
3 3 4 3 3 4 3 3 1

なんとなく3組に分かれている気がしたので投げると通る。通ってから正当性は理解しました。

残りの時間は分からないFGHを考えていた。

結果は5完21位で国内予選通過でした！同校から参加していたATELIERも通過していたので一緒にアジアまで頑張ります。

反省

順位表を見てBの様子を聞いたのは良かったが、Cに対してしたのは多分邪魔なだけだった。難しすぎる……

古い出力をちゃんと取っておく。

落ち着く(どうやって？)

その他

九死に一生を得たという感じで非常にしんどかった。

めっちゃ人々を冷や冷やさせていたらしい。僕が一番冷や冷やしていましたけど。

ちなみに4完で終わっていると予選落ちです。危なかったね。

でぃぶ君にも全方位木DPを投げていいことが分かった。嬉しいね。

ちょくだいさんへ AtCoderで沢山問題解いてるのにひやひやさせてごめんなさい。



以上の内容はhttps://olphe.hatenablog.com/より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14