みんプロ2019参戦記
こんばんは、Harsakaです。
今回は昨晩開催された『みんなのプロコン 2019』に参加した感想を書きます。
序盤
開幕。実力(緑色)的にこういう企業コンはAB早解きまででもそれなりの価値があるので配点の低い方から逐次見ていきます。
A問題。日本語が少し怪しく一瞬困惑したのですぐにサンプルを読む。サンプルまでが問題文だと思って読むのが誤読減のキーだと思っています(そう思いながら数々の『目がついていない』系のミスをしているわけですが...)。
そういうわけで例1を読んで問題文に戻り文意を理解。Kコの整数の選び方の最善手は小さい方から全ての奇数を選択することなのでn>=2*K+1なら"YES", そうでなければ"NO"でAC。(2:24)
最近、「自明！」つって等号付近をミスってWAしたことがあったので入念にSampleを確認してたらこのくらいかかったけど5分以内ならこの方が早いので良しと考えます(ちょっと遅い気がするけど)。
B問題。一筆書きなので準オイラー閉路...などと考える必要はなく、4頂点に辺が3本という条件から、次数3の点がなければ"YES", そうでなければ"NO"と単純な条件が出てきます。
証明は...
- nコの辺で連結可能な異なる頂点数は高々n+1コで、そのような辺の張り方は各点の次数が両端が1それ以外が2となるようなものに限られる。
- 今、 (辺の本数)=(頂点数)-1より1のような辺の張り方をすることが一筆書き可能の必要十分⇔端だけ次数1でそれ以外は次数2。
言語化が下手すぎるしそもそも証明になってるのかアヤシイが...まぁ無駄な辺を張らないようにすればOK(は？)。
Submission #4206426 - Yahoo Programming Contest 2019
mapで次数を調べてAC。(6:29)
400点問題。ビスケットを叩いて増やすかレートA:Bの交換を行うかの二択の手順を踏みビスケットの枚数を最大化するという問題。誤読が怖いのでSampleを見に行くと...。
・ビスケット 枚を 円に交換する。すぬけ君は、ビスケット 枚と 円を持っている。
・ビスケットを叩く。すぬけ君は、ビスケット 枚と 円を持っている。
！？w
虚空を叩いてビスケット増やすの好き
— はーぷよ (@har_puyo) February 9, 2019
まぁ仕様だよな...???と思いつつ読んでる瞬間に質問が飛んで行ったので見に行ってみる。
etonagisa(大学同期)が質問してて笑っちゃった。ということですぬけくんは虚空からビスケットを生み出す錬金術師でした。
さて問題に戻りましょう。ビスケットを増やす手段は先述の通り2つあります。
- 無心でビスケットを叩き続ける:t回でビスケットは1枚からt+1枚に増える。
- A枚までビスケットを増やし、A枚のビスケットを1円に交換し、手に入れた1円をB枚のビスケットに交換する。この場合、1枚からA枚に増やすまでに(A-1)回、1円を介してA枚をB枚にするのに2回手順がかかるので合計A+1回の手順がかかる。
どちらの戦略でビスケットを増やす方が効率的かを考えます。戦略2はA+1回の手順を必要とするのでK<A+1の場合そもそも実行できません。したがってそのときは戦略1をとり最大値はK+1です。また、A+1回ビスケットを叩けば1枚からA+2枚にまでビスケットを増やせるのでB<=A+2の場合も戦略2を取る必要がなく、最大値はK+1となります。
さて、残りの場合は戦略2を取った方がいいことがわかりました。手順K回の中で何度(A+1)回の手順を踏めるかなのでfloor(K/(A+1))を計算し...
こうしてfloor(K/(A+1))*(B-A)+K%(A+1)みたいなことをしたら入力3に殺されます。
出力例より明らかに小さい値が出てパニック。型をlonglongにしてるかどうかなどチェックするも問題はなく...適当にA*Bを電卓に投げたら解答出力と同じケタの数が出てきたところで明らかに計算がおかしいと気づきます。
何で違うんだ～？とカラっぽの頭を回していると、1回目のA→B交換をした後は手元にB枚のビスケットが残っていることに気づきました(当たり前だろ)。虚空からビスケットを生むのが印象的すぎて手元にはいつも0枚か1枚しかビスケットがないみたいな固定観念があったのが敗因な気がしてます。ともかく2回目以降の交換はビスケットを叩いて増やす必要がなく、ひたすら2回叩いてB-A枚増やす作業を繰り返すだけです。最後に1回手順猶予がある場合は1回叩いて1枚増やします。
Submission #4211338 - Yahoo Programming Contest 2019
これを愚直に実装しAC。(31:12)
問題の複雑さにしては少し時間かかった気がしたけど変なWAを生やすこともなく通せたのでこの時点でまずまずの感触でした。
中盤・終盤(虚無タイム)
さてD問題(600点)。過去のAC取得点の最大値は500なのでこれを通すと金星です。
ジャイアントキリング目指し意気込んで問題を読むと...
『すぬけ君は 個の耳を持っており』 1<=L<=2*10^5
『すぬけ君は、座標が整数 を用いて と表される点を通るたびに、 番目の耳に石を 個入れます。』
『すぬけ君の耳をひとつ選び、石を 個入れる』
『石が 個以上入っているすぬけ君の耳をひとつ選び、石を 個取り出す』
ヒェッ...。すぬけ君ただのバケモノだしりんごさんはすぬけ君を蹂躙してるし何なんだコレはと震える(企業コンでこんなはっちゃけていいのかなｗ)。
設定が異様すぎて問題文に目を向けられないのでサンプルの数字を睨んで問題を解くことにしました。まずは両端。端の方に比ゼロの目標値kがあってその隣に0がmコ続く場合、散歩によってkコの石を入れたあとにその次の非ゼロ値のところにたどり着くまでにmコの目標値0の耳に1つずつ石を入れると最後にりんごさんはm回の操作を要します。一方目標値kの耳を放置してその次の非ゼロの耳から目標値に近づける散歩を行う場合、最後にりんごさんはk回の操作を要します。なのでmとkの大小を見たりすると良さそう？
しかしこれは当然両端について見るべきだったり、二つ目の非ゼロの連続とかにはどう処理するの？みたいな多数の謎が生えて僕の手には負えませんでした。
次にサンプル2と3を睨みます。サンプル2より、偶奇偶のように2つの偶数に奇数が挟まれていると散歩の仕方によらず必要な操作回数が増えるみたいな予想がつきます。
サンプル3からは端の偶奇はどうにでもなることがわかります。また、散歩の開始を、目標値が偶数の耳から始め同じ耳のポイントで終わるとすると、複数の偶数目標値がある場合もうまく最後の操作を0にできるみたいなことがぼんやり浮かびます。しかしこれも厳密にはどういう条件が働いてそうなるのかがわからず実装には全く活かすことができません。
いくら考えても厳密性に欠ける曖昧な予想しか出てこず、90分が経過しコンテストが終了しました。
感想
過去の反省からAとBを保守的に解いて0WAで通せたのはよかったです。Cはもっと早くとけたはずだし20分弱で通せば青パフォだったので頭を鍛える必要があると感じました。TLの感想戦を見るとDはDPのDをやると良かったり、順位表を見ると人々はDよりF(900)の方を通しまくっていたりと緑には見えていないものがいっぱいあるんだな～と思いました。
春休みは蟻本読んだり400の精進したりで一刻も早く水色を目指していきたいですね。読了ありがとうございました。
