Codeforces Round #706 (Div. 2)
こどふぉ人生初のABC問題3完できました！やったぜ。でもレートの伸びはいまいちだぜ。そのうち水色行きたいな…
持ち時間の使い方はA問題に30分、B問題でハマって1時間、C問題10分程度と変な配分になりました。B問題は全然バグが取れなくて、一旦C問題に移動したのが吉と出ました。良かったー。
A. Split it!
今度は東方厨かつドキ文好きのWriterか…たまげたなぁ… 前回ぺこらが出たと思ったら今度はにとりだと…？しかもサンプルケースの例文、「dokidokiliteratureclub」に「imteamshanghaialice」って遊びすぎやろwwwおかげで緊張解けたけどwww
中身については、まず問題文読み解くのに5分ぐらいかかりました。AtCoderもですけど、問題文をざっと読んだらサンプルケースの入出力及びその解説見た方がスムーズに理解が進む気がします。ただCodeforcesはサンプルケースがめっちゃ簡単なケースばかりで、想像力を働かせないとプレテストで即死するイメージですね。
最初の実装方針は、「回文ならおｋなのね」って判断して文字列Sの頭から真ん中までとお尻から真ん中までを1文字ずつ比較して完全一致か判定という考え方でしたが、プレテストでWAでした。よくよく考え直すと、文字列Sの頭とお尻からk文字までが一致してたら真ん中はどうとでもなるのでは！？と気付き修正。AC。
B. Max and Mex
nとkの範囲が結構大きかったので計算量意識しないとすぐTLEになるなぁと思い、アルゴリズムを15分ぐらい考えてた気がします。結局最初に試したのは、値が全部0で長さの配列を作って、Sの各要素をインデックスとして配列の値を1に変えていくことで、値がまだ0のインデックスで最小のものをmexにするという操作をk回繰り返す、という実装でした。それだけだとプレテストでTLEになったので、k回ループする前に終了できる条件とかを書き足していって計算量はクリアできたのですが、なぜかプレテストでREがずっと取れず時間を使い続けたので、諦めてC問題に挑みに行ってしまいました。
最終的にmexを求める時に配列を使うのではなく、setの中に要素があるか否かで判定することでなんとかクリアできました。初めからset使っときゃよかった。この問題だけで1時間以上時間使いました。
REになった原因は未だ分かっていません…配列のサイズがでかすぎたから？だとするとMLEになるのでは？とか考えましたが、よく分かりません。ちゃんと検証したい…でもデータセット作るのめんどくさい…
C. Diamond Miner
ちょっと紙に書いてイメージしてみたら、なんとなく線が交差すると良くなさそうだな、遠くのXと遠くのYから順に結んでってやるのが良さそうだなと感じたので、鉱夫とダイヤの座標をそれぞれ絶対値でソートして貪欲に距離計算していったらサンプルケース通る答えができました。そのまま提出したらプレテストもパス。え…C問題簡単じゃない…？と驚きました。
てかこれまで受けたこどふぉのC問題、確か3回連続で貪欲法使う問題なんですけどこれはつまりそういうことなんですかね…
東日本大震災から10年経って思うこと
完全に話は変わりますが、今日は東日本大震災からちょうど10年ですね。
僕は当時学会発表で筑波に居て、確か筑波は震度5強程度で被害はそれほど大きくなかったのですが、それでも死を予感するには十分すぎるほどの激しい揺れを体験しました。 震災当日は交通網が麻痺したため、筑波のホテルのロビーに一晩身を寄せさせて頂きました。ホテルの従業員の方々をはじめ、現地ではいろんな方に本当にお世話になりました。その節は本当にありがとうございました。
そして震災の夜、余震が続く中MP3プレイヤーのFMラジオ機能で情報収集していたところ、細かな数字は失念してしまったのですが、「福島県の海岸沿いで200名の方の遺体が発見された」という速報が入ってきて絶句しました。あの衝撃はきっと一生忘れることはないと思います。血の気が引いて、日常が一変してしまったことを痛感しました。明くる日にタクシーや新幹線を乗り継いで安全な実家に帰り、温かいご飯を食べながらテレビで津波の様子を呆然と眺めていたら、あまりの落差に自然と涙が溢れてきました。
あれから10年、未だに震災の傷痕が各地で癒えきっていない中、自分が今日も幸せに生きていられることに改めて感謝したいと思います。微力ではありますが、今後も寄付や特産品の購入等で現地を支援していければ、と考えています。このブログに巡り逢った方で一緒に支援活動してくださる方が増えたなら、とても嬉しいです。
最後に、震災で亡くなられた方がどうか安らかに眠られることを祈って、黙祷を捧げさせて頂きます。
以上です。