ツバサの備忘録

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

ARC029 D - 高橋君と木のおもちゃ

問題
提出コード

解法

まず、整数を置く回数は、全体で\min(M,N)回になります。
葉から見ていき、追い出したい数字が置いてある頂点に数字を置く、という操作を繰り返すことでこれは達成できます。
また、ある数字を追い出したいとき、今置いてある頂点より親にあるものは全て追い出されてしまいます。
これにより、葉の方から追い出すか追い出さないかを決めていけば、何か計算できるかもしれない、ということがわかります。
また、数字を置く回数を決めると、tは大きいものから貪欲に選べることもわかります。

  • dp[i][j] = 今見ている頂点がiで、追い出すと決めた頂点がj個あるとき、残すと決めた数字の総和の最大値

というDPを考えます。
すると、
dp[i][j] = \max \left( \sum dp[to][k] \right) (ただし、toiの子、1 + \sum k = j)
という遷移が成立することがわかります。
例外的に、j = 0の場合のみ、dp[i][0] = \sum dp[to][0] + s_{i}となります。
この遷移は、二乗の木DPの形になっているため、計算全体でO(N^{2})となっています。
この計算が終わったら、
dp[1][i]と、tの上からi個とったものの和について、最大値を計算することで答えが求まります。

感想

初手何していいかわかりづらい問題だったのですが、考察を進めていくと綺麗になったので面白かったです。

競技プログラミングを始めて3年が経ちました

2/7にAtCoderで初ACをしたようなので、3年になりました。 この手の記事を書くのは初めてなのですが、自分の昔を振り返りたいときに残っているデータがほとんどなかったため、記録しておくことにしました。
データは2/6の19時時点のものです。

AtCoder

f:id:emtubasa:20210206185421p:plain

f:id:emtubasa:20210206185508p:plain

f:id:emtubasa:20210206185558p:plain

f:id:emtubasa:20210206185538p:plain

f:id:emtubasa:20210206185619p:plain

f:id:emtubasa:20210206185647p:plain

f:id:emtubasa:20210206185656p:plain

こうしてみると、やっている時期とやっていない時期の差がはっきりしていますね…

ヒートマップから、コンテストに出ているのだけはわかるのが面白いです。

AOJ-ICPC

f:id:emtubasa:20210206185913p:plain

国内予選後、全く手を付けていないので来年に向けてまたやっていきたいところです。

Codeforces

f:id:emtubasa:20210206190307p:plain

夕方~夜のコンテストをお待ちしております。

ARC 095 E - Symmetric Grid

問題
提出コード

解法

それぞれの行に含まれている文字の種類とその個数の状態関係について見てみると、
行をswapしても、列をswapしても、個数自体に変化はないことがわかります。
最終的に点対称になるので、先ほどの状態の一致不一致を使って、行と列それぞれで回文を作れることが必要になってきます(これは必要条件であり、十分条件ではありません)。
この条件で網羅しきれない入力は以下のようなものです:

3 4
abba
cddc
baab

行についてみると、文字の状態が既に対照的になっていることがわかります。列についても同様です。しかし、これは点対称になっておらず、回転させると四つ角が一致しません。
ところで、入力についてよく見てみると、行数は12ととても少ないことがわかります 。H/2個のペアを作る、ということを列挙することを考えると、H=12であった場合、
\frac{12 \times 11}{2} \times \frac{10 \times 9}{2} \times \frac{8 \times 7}{2} \times \frac{6 \times 5}{2} \times \frac{4 \times 3}{2} \times \frac{2 \times 1}{2} \times \frac{1}{6!} = 11!! = 10395
通りとなります。実際にDFSでペアを作成するときは、まだペアにしていないもののうち、片方は行番号が一番小さいものを必ず使う、とすることで無駄なく列挙できます。
点対称にするためには、W/2個の列番号のペア(i,j)を作成し、今作成した全てのペア(奇数で漏れたものについては自分自身)について、ペアの文字列がstだった場合に、s_{i} = t_{j} かつ s_{j} = t_{i}となる必要があります。
逆に、これができれば点対称にすることができます。
この判定は、行のペアを決めた後、全ての行ペアに対して条件を満たすような列ペアを辺で結んだグラフを考えると、連結成分のサイズが奇数になっているものの数が1以下になっているかどうかでできます。
全ての行ペアの決め方に対して、上記の判定を行い、1つでも1以下のものがあればYES、そうでなければNOになります。

感想

最初の嘘解法が1ケースしか落ちていなかったので、ずっとコーナーケースを探していました…
ペア列挙がN!!で求められることをよく忘れるので、ここらできちんと覚えておきたいです。

AGC051 B - Bowling

問題
提出コード

解法

まず、(0,0), (1,1), \ldots (9,9)という置き方を考えます。すると、下の図のように、対角線上に点が10個並びます。この時、A, C, Dは同じ個数だけ見えて、Bだけ1個しか見えません。よって、この置き方を1つのブロックとして大きな1個の点とみなすと、このブロックを用いて、A, CがDの1/10以下になるような配置を考えればよいことになります。
なので、これ以降Bのことを気にする必要が(ほぼ)なくなります。
f:id:emtubasa:20201228121550p:plain


上記のブロックをたくさん置いたときに、Dから見える個数がAとBの10倍になるようにしたいです。
一番簡単そうなのは、x座標とy座標を10個ずつ決め打ち、100個の点をプロットしたとき、 x + yが全て異なるようにする、というものです。
これは、xが1の位、yが10の位、となるようにしてxは0,1,\ldots 9、yは0, 10, \ldots 100を選べばよいです。
あとは、先ほどのブロックの大きさが10 \times 10なので、和が重複しないように選ぶx座標とy座標の微調整を行えば、1000個の点をプロットしたときにA~Cが100、Dのみ1000、という状態を作ることができます。
具体的には、xは0,20,40, \ldots、yは0,200,400, \ldotsとすれば問題ありません。

感想

難しかったです…でも解けた時はなるほど、となりました。面白かったです。
斜めにできるだけ置かないとBがかなり強かったのですが、そうするとACが半分にしかならない、という状態が多発していました。今回のコンテストはかなり冷静でいられたと思ったのですが、それでも時間がかかっているので悔しいです。

AGC049 B - Flip Digits

問題
提出コード

解法

できる操作が、

  • 1 をひとつ左に動かす

  • 連続する1 を消す

のどちらかとなっています。
また、右側にある 1 が、一つ左側の 1 を追い越すことはできません(そもそも、追い越したいのであれば、左側の 1 を動かせばよいです)。 そのため、元々Sで与えられた 1 の順序は変化しないまま、左に移動するか、消えるか、その位置のままか、のパターンしかありえないことがわかります。
S_{i}1 のときに左に移動させる(もしくは据え置き)パターンは、それより左側に、まだ位置を確定させていない 1が存在しないが、T_{j} (j \leq i)1 となっているものが存在するパターンです。jが最小となっている箇所に優先的に移動させないといけないため、i-j回の操作が必要になります。
S_{i}1 のときに消すパターンは、上記のようなjが存在しないときです。どこへ移動させてもTと一致することがないので、S_{k}(i \lt k)1 となっている最小のkを見つけ、その 1 と合わせて打ち消します。これにはコストがk-iかかります。
以上のことをシミュレートし、最終的にSTが一致すればよいです。
queueを2つ使い、STでまだ消すべきなのに消してない/ 1にすべきなのにS_{i}1になっていない位置をメモし、消すべき1から優先的に上記の処理を行います。

AGC010 D - Decrementing

問題
提出コード

解法

わかりやすい部分、つまりNが小さい方から考えていきます。

N = 1のとき

1回の操作で必ず1減少するので、明らかに、A_{1}の偶奇で答えが判定できます。
奇数であれば後手勝ち、偶数であれば先手勝ちです。

N = 2のとき

A_{i}のどちらかが1であった場合、先ほどと同様、もう片方の数字の偶奇で判定でき、奇数なら後手勝ち、偶数であれば先手勝ちです。
そうではない場合を考えます。順序は関係ないため、A_{1} \lt A_{2}であると仮定します。
A_{1} = 2のとき、問題の条件より、A_{2}は3以上の奇数になります。
この時、A_{1}を先手が選ぶと、A_{1}が1になり、これ以降はA_{2}を減らすことしか選べなくなります。ここで、A_{2}は開始時点で奇数であることが保証されていたため、結果としては必ず先手が勝つことになります。
A_{1} = 3のときも見てみると、遷移先の勝敗を照らし合わせることで、
(3,4),(3,8),(3,10)は先手勝ち、(3,5),(3,7)は後手勝ちであることがわかります。
この結果を踏まえると、どちらか片方が偶数であれば先手勝ち、奇数であれば後手勝ちであると予想が立てられます。
これが正しいことを証明していきます。
ゲームの最終状態は(1,1)です。よって、両方奇数であれば負け、ということになります。
現在のゲームの状態に偶数が含まれている場合、その偶数を選んで1減らすことで、両方の数字が奇数になります(割り算で偶奇は変化しません)。
逆に、両方奇数である場合、どちらを選んでも、必ず偶数が残ってしまいます。
よって、偶数が含まれた状態でターンが回ってきた場合、相手に必ず両方の数字が奇数である状態を押し付けることができ、逆にそれがおしつけられた場合、相手には偶数が残った状態でターンを渡すことになります。
これにより、N=2のときは、偶数が含まれていれば先手勝ち、そうでなければ後手勝ちであることがわかりました。

N \geq 3のとき

A_{i}に1が含まれている際は、1ずつ減っていくだけなので、これは先ほどまでと同様に答えを求めることができるため省略します。
ここらから状態のパターンが多くなり複雑になっていくので、実験コードを書いて実験をしてみます。すると、Nの偶奇でパターンがわかれていることがわかります。

Nが偶数のとき

A_{i}に含まれる偶数の個数の偶奇で勝敗が決まっていることがわかります。
偶数の個数が奇数であれば先手勝ち、偶数であれば後手勝ちです。
奇数個の状態で回ってきた人は、偶数を選び1減らすことで必ず相手に偶数個の状態でターンを回せます(選んだ偶数が必ず奇数になり、最大公約数が偶数になることはありません)。
逆に、偶数個の状態で回ってきた人は、偶数、奇数どちらを選んで1減らしても、偶数は奇数個になってしまいます。こちらのパターンも、Nが偶数のため、奇数が必ず1つ含まれることになり、最大公約数が偶数になることはありません。
これにより、Nが偶数のときには、A_{i}に含まれる偶数の個数が奇数であれば先手勝ち、偶数であれば後手勝ちであることがわかりました。

Nが奇数のとき

こちらも基本的には偶数パターンと同じ見た目をしています。
偶数の個数がN-1でなければ、上記と同様の作戦をとることで勝敗が決まります。
しかし、偶数の個数がN-1の場合、以下のような例が考えられます:

5
2 4 6 8 11

このようなパターンのとき、先手は11を選んで操作を行うと、

1 2 3 4 5

となります。これは、本来先手から始めた場合に後手が勝つパターンです。1回先手が操作をしているので、上記のケースは結局先手勝ち、ということになります。
つまり、N-1個の偶数があった場合、1つだけある奇数を選んで操作することで、勝敗がひっくりかえることがあります。このパターンのみ、1つの奇数を選んで操作をする、ということをシミュレートし、勝敗がわかるまで繰り返せばよいです。
必ず偶数の最小公倍数になるため、一度の操作で全ての数字は半分以下になります。よって、操作はO(\log A_{i})回で収まり、十分間に合います。

これで勝敗の判定方法がわかったので、まとめます。

  1. Nが1のとき
    A_{1}の偶奇で判定します。

  2. 上記以外で、A_{i} = 1となるようなiが存在
    \sum_{i} (A_{i} - 1)の偶奇で判定します。

  3. 上記以外で、Nが偶数、もしくはA_{i}の偶数の個数がN-1でない
    偶数の個数の偶奇で判定します。

  4. 上記以外(Nが奇数かつ、A_{i}の偶数の個数がN-1
    残った奇数を選び操作をするとしてシミュレートし、上記のパターンに帰着できるまで繰り返します。

という形です。

感想

苦手なゲーム問題で、実験コードを組みつつきちんと通せたので、良かったです。

ICPC2020国内予選 参加記

とまとさん、るぎうさんとの三人で出る。正直、AtCoderで黄色三人のチームは弊学でここだけで、最近は自分の調子も良かったので何もなければ通っていると思っていた。
コンテスト前、大学に来て出ている他の5チーム(?)全部に挨拶してまわる。イケメンだったsuzuken君が眼鏡をかけてさらにイケメンになっていて、気づかなかった。ごめん。

コンテストが始まる。
...
リロードを押す。コンテストが始まる。
...
問題が見えない。びっくりしてコーチの元へ向かうと、他のチームの代表者も来ていた。安心(安心ではない)。
部屋に戻る。るぎうさんに、コンテストサイトは見えた(問題はまだ)と言われ、改めて報告しに行く。何かあったら教えてくださいと言い、戻る。
部屋に戻る。るぎうさんに、問題が見えたと言われ慌てて問題を開く。Aはとりあえず適当に書いてしまえばいいや、と言い書く。AC。

Dを開く。構文解析が見えたので身構える。と同時に、とまとさんから「B問題が読めない><」と言われる。落ち着いてもらうため、僕がBを読み、とまとさんにDを押し付ける。読んだらUnionFindを貼ればいいと書かれていたので、ICPC特別ルールに感謝しながらライブラリをぺたり。AC。

Dへ行く前にC担当のるぎうさんに声をかける。るぎうさんはpython使いで、Cはどうやらc++の方がはやく終わって良い、ということなので僕が実装をする。計算量があんまり計算できなかったけど、まぁ適当に枝刈りをしておけば間に合うだろう、と適当にコードを書く。かなり進みが遅いが、しばらく待つと実行が終わる。AC。
順位表を見ると、弊学TOP3チームが仲良く並んでいて、ここからが勝負だと確信する。

3人がDへ集合する。うんうんうなる。解けない。
Eをチラ見すると、ICPCでは初登場?のMOD数え上げ。チームの数え上げ問題枠だったので、嬉々として取り組む。解けない。
順位表から、EよりDの方がいいと判断し、渋々戻る。
引き続き、3人でうなる。解けない。
途中、僕がEに再び挑んだり、Fが通っていたのでFをとまとさんに読んでもらったりしていた。
気づいたら残り30分ほどになる。
るぎうさんの一言をもとに、正当性に確信を持てない解法が生える。
とまとさんに構文解析の解析パートを書いてもらい、自分が本編を実装する。この時点で説明を端折った結果、僕以外が解法を理解していなかったのがまずかった。
実装が終わるが、サンプルが合わない。焦る。このあたりで、他所から歓声があがる。順位表を見ると、UHISHIROが5完していた。終わった…
解法を疑い、別の変な解法を編み出す。もちろんサンプルが合わない。
とまとさんがこっそりFを実装していたらしく、サンプルがあう。が、実行するとREになったらしい。
Dも振り出しに戻り、そのままコンテスト終了…

終わってからUHISHIROのDを聞く。最初に生えた解法があっていた。なんで…
Fもとまとさんに解法を聞くと、すごくそれっぽい。もっとはやくFを教えてあげられたら…?
EもUHISHIROに聞く。30×30まではできたけど、こんなの思いつかない。数え上げが多少は得意だと思っていたけど引退…
その後も感想戦は続く。
そもそもDをバグらせなければ…?
Dの解法をきちんとるぎうさんに説明していれば…?
あるいは、とまとさんをDに引き戻して一緒にデバッグしていれば…?
この1年何をしていたの…?
競プロなんてやってないで、真面目に学業に取り組むべきだったのでは…?
とまとさんとるぎうさんは最後の年なのに、僕がA~Cやって終わりでいいのか…?
頭の中をいろいろなことがぐるぐる駆け巡る。感想戦の間、ずっと「うー」とか「あー」とか言っていた。

感想戦が長引いたので、UHISHIROメンバーと夜ご飯を食べる。諸事情によりうどんだったので、通過記念に奢ってあげようと思っていたが、すっかり忘れてしまった(今度やる、忘れていたら教えて)。
途中、suta君が「あ、あれを注ぐのか!」と言って急に席を立つ。何かと思えば、温かいうどん用の出汁を注いでなくて、うどんだけで食べていたっぽい。浮かれすぎ?
通過チームと一緒にごはんを食べていて、一人だけお通夜ムードだった。ごめん。


帰り道、1時間電車に揺られる。
ここでも頭の中でいろいろなことが巡る。
自分だけあと2回あるのに、とまとさんとるぎうさんのラストチャンスを奪ってしまったという思いがやっぱり強く、泣きそうになる。最近好きなReoNaさんの曲が、割と悲しめの曲が多いこともあり、イヤホンで聞いていて追い打ちをかけられた。電車なのでなんとか耐える。去年の学生コン予選で落ちた時は友達に電話をかけて泣いてしまったので、少しはメンタルが成長しているかもしれない。
誰か友達にラインをしようかとも悩んだ。そういえば、一緒に出ていた競プロ友達全員大学に居たのに、コンテスト後は誰も会いに来なかった。気を使ってだったのかな、ごめん(最近レートを振りかざして調子に乗っていたのでそれのせいかも、これもごめん)。いろいろ悩んだ結果、最寄り駅あたりでようやく、ICPCの後にラインをくれていた人に話しかけた。ちょっとメンタルが落ち着いた。

家に帰ると、親に順位表を見られていたことを知る。いろいろ話すと、また悔しさがこみあげてきて泣きそうになったので、慌てて自室に逃げてこの参加記を書き始めた。

とはいえ、幸い、悔しさをばねにして頑張ろうって思えるタイプみたいなので、またここから頑張って行こうと思う。ラストチャンスだったとまとさんとるぎうさんの分も、来年リベンジしたい。来年は僕が独りぼっちになってしまうので、まずはチームメイトを探すところから始めなければ…
ところで、競プロに熱中していたせいで学業がピンチらしい。助けて。
(お気持ち成分が多かったので普段と違う口調です。読みづらかったらごめんなさい、読んでいただきありがとうございました。)