2021年2月20日土曜日

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

  終了五分前に7ペナの末、FをACして全完。全完できたとはいえ、ちょっと喜べない出来。


D - Base n

 二分探索の上限の設定と、Xが一桁の場合をミスって1ペナ。
 後者については、1WA出した後、Xが一桁なら答えが無数にあるのでは? と思って問題文を見直したら、「Xをn進法表記の数とみなして得られる値」が何種類あるか問われていることに気付きました。
 パッと理解するのは難しい文章だと思うので、1ペナで切り抜けられたのならまあ良いか。

F - Potion

 部分和っぽい問題なので、一目DPを考えたくなります。ただ、素材の個数が絡んでくるから上手くDPできなそう……? と分からなくなり、使わない個数は少なくてもなぜか上手くいったりするのかな? とか考えてしまった。

 実際はDPでOK。
 素材の個数のせいで分かりにくいなら、素材の個数を決め打って、それぞれの場合についてDPすれば良いです。計算量が増えそうでちょっと不安だけど、$O(N^4)$としてはかなり軽くなるので、PyPyでも通ります。

 落ち着いて見れば自然な解法なんだけど、長いこと迷走してしまった。

2021年2月19日金曜日

Codeforces Round #703 (Div. 2)

  Dまで四完。順位はそこまでひどくはなかったけど、Eが見えなかったのはひどい。


E. Paired Payment

 制約をよく見ましょう!
 $w_i$は50以下です。

 各頂点について、最短距離と、wの値が1~50のときの一歩手前の値を持っておけば、ダイクストラできます。

 wに上限があることは十分考えられるのに、制約をあまり見ずに考えていたのはひどい。
 冷静になれば、CやDより典型でACしやすい問題だった気がする……。



2021年2月16日火曜日

Educational Codeforces Round 104 (Rated for Div. 2)

 遅刻してAで誤読したためB~Dの三完で終わるという酷いことに。B~Eの速度はまあまあだったからよし、とするしかないか。


 そして、Eも本当にソートするだけの実装問題だし、Aの誤読以外でツイートに付け足したい内容がないです。

2021年2月10日水曜日

Codeforces Round #700 (Div. 1)

  B2までの三完でした。レートは若干下がったものの、Aで三十分かかったことを考えれば良い出来かと。


A. Searching Local Minimum

 Aで出題されて、インタラクティブなら、二分探索系以外ありえない! ……と問題を開いたときすぐ思ったけど、解くまでかなり時間がかかってしまった。
 しかし、「二分探索を使いそう」以上に、この問題から得るべき知見はない気もする……。

 「極値を求めるから三分探索」としてシステムテスト落ちした人は結構いたようです。noshi91さんの昔のツイートが話題になっていた。
 うーん、でも今回みたいな離散的なやつなら、三分探索で極値が求まるっていう気はあまりしないので、私は引っ掛からないかな……。凸関数じゃないと求まらないイメージがあったけど、この記事を読むと、それで大体正しそう。

B. Painting the Array 

 B1もB2も最初に考えた解法は間違っていた。(B1は本当にただの貪欲を、B2はDPの遷移がおかしかった)
 けど、WAを出している人が多かったのを見てそれを提出せず、全パターンの色塗りを試すを愚直全探索&ランダムケースでテストしたおかげでACできた。

 このテストを書かなければ正しい解法に至れたかも怪しいので、今回は、愚直を書いたのは正解だったんだと思うけれど、どういうときに書くべきなのかは分かっていない。それなりに時間がかかることだしね。

C. Continuous City

 この問題の類題。
 類題経験があったから解けるべきだった気もするけど、ちょっと条件が違うので、「2ベキを使う」ということ(これは、類題経験がなくても分かる)以外は生かしにくいので仕方ない気もする。

 二頂点間にパスは一つしか引けないが、引くパスの数は制限されていない、というのが重要。

・4→3→2→1→ゴール

 というパスを考えたとき、

・1からはゴールに長さ1のパスを。
・2からは1とゴールに長さ2のパスを。
・3からは2と1とゴールに長さ4のパスを。
・4からは3と2と1とゴールに長さ8のパスを。

 という風にしていけば、1から15までの長さのパスは作れる。スタート地点から、これら全てにLのパスを繋げれば、スタートからゴールへ、長さLからL+15のパスが作れる。

 それだけではLからRの全てのパスは作れないけど、後の残りは、スタートから各ノードへ割り振る感じにすれば良い。
 先の決め方で、

・1からは長さ1~1のパス
・2からは長さ2~3のパス
・3からは長さ4~7のパス
・4からは長さ8~15のパス

 が出ているため、各ビットが立っているかを見る感じで決められる。
(なお、最初からこの決め方をするのは負辺が必要になるため、無理)

2021年2月7日日曜日

AtCoder Beginner Contest 191

 D, Fが解けずに終了。Fで1caseTLEだったので粘ってしまったが、原因がよく分からず、結局TLEを除けなかった。


C - Digital Graffiti

 あるマスが角の黒マスになるのは、ある頂点を見て、その周囲4マスのうち、「1マスが黒マス、または、3マスが黒マス」になるとき。
 結構難しいと思う。結構すぐ思いつけて自分で驚いた。


D - Circle Lattice Points

 誤差が重要な問題なので、X,Y,Rに予め$10^4$してから考える……というのは思いついた。
 が、

・X=int(X*10**4)

 としてたのがダメで、

・X=round(X*10**4)

 のようにしたら通った。

X=0.0024のとき、X*10**4は23.999999999999996になるのですね。気を付けないと。

F - GCD or MIN

 解法自体はツイートした通りであっていたのだけど、実装が悪かった。
 kyopro_friendsさんのツイートの通りで、約数列挙とgcdを取るのを同時にやることで計算量が落ちる。(私は、ツイートを見る前に実装を見て、なるほど~、となった)

 二つのパートを上手くマージすることで計算量が定数倍落ちることは結構あるけれど、オーダーが落ちることは結構珍しい気がする。

2021年2月5日金曜日

TopCoder Marathon Match 123

 参加していました。


 前回のMarathon Match 122も参加したのですが、実装終わると思ったものが書き終わらず、時間ギリギリで出したコードがバグあり&エラー出力消し忘れ(のため大きいサイズだとTLEする)がひどく、レートを大きく落としてしまいました……。

 それがショックだったので、今回は初日からちゃんと参加。とはいえ、初提出が終了日前日と、余裕はあまりありませんでしたが。

 ルールは、盤面のどこでも二点をSwapできるマッチ3ゲームで、1000ターンでどれだけ点数を出せるか(点数のルールは説明省略)。
 ビジュアライズが宝石になっていたので、「コラムス」か? と思いましたが、あれは斜めも消せました。

やったこと


 Xターン後、スコアを最大化できるようなSwapを探索……とかだと計算時間が間に合わなそう(特にPythonだと)なので、その方針はあまり考えず、適切なパターンを作って、それに当て嵌める方針でいきました。
 ツイッター等で他の人の解法を見る限り、その方針は正しかったよう。

 ただ、そのパターンへの組み換えへの実装には結構苦労しました。
 一連鎖目から色が揃っているかを見ていき、揃っていなければ、後の連鎖のやつの中で、その色を持っているやつからもらう……みたいな方針です。
 どの色で組むかは、その数個の中で最も多い個数のやつを採用するようにしました。

 パターンについて。
 点数計算を見ると、長い連鎖を組むのが良いですが、長いサイズの消しも一回くらいはあると良さそう、ということで、二連鎖目に横長の消しをするようにしています。暴発の防ぎ方が分からず、長い連鎖が組めなそう……と分かってからはそこを重視しました。
 ただ、横16マス消しも可能だということが分かったのが最終日夜だったのは痛かった。もっと前に気付いていれば、パターン作成を詰められたかもしれません。

 自分のパターンは、二連鎖目に長いサイズ(最大N-1個)を一番下の段で消して、そこから3個ずつ、前の連鎖に一個か二個重なるように置いて、連鎖を続けていくというもの。そのどれを選ぶか、というのを目で見て決めました。ただ、適当に置くと(連鎖ごとの色が全て異なっていても)連鎖中に暴発してしまうことがあるので、そこはプログラムでチェックしています。
 そうやって作ったパターンの中で、実際に実行したとき点数が良さそうなものを採用しました。

反省点

 点数が伸びなかった原因ははっきりしていて、パターン構築が甘かった、これにつきます。もちろん、パターンへの組み替え方の実装なども良くないのですが、一番の原因はそこ。
 一番下の段ではなく、盤面の中程で横長の消しを行い(それも、N-1個ではなく、N個を数段同時にやってもいい)、そこから下に向かって連鎖を繋げていくような方針なら、もっと安全に長い連鎖を組めた模様。

 パズル部分で考察が及んでいなかった、というのは残念。

 パターン次第ではもっと点数が伸びるはず、とはずっと思っていたのに、そこを詰められなかったのは良くないですね。

 実装力(や言語選択)のせいで負けた、と言えるような成績を取りたい。今回の自分の方針だと、他の言語に書き換えたとしてもほぼ点数は伸びません(一応、最後着火する前に、一手で連鎖が増やせるSwapがあるか調べる探索を入れているので、その部分は伸ばせるかもしれませんが、誤差の範囲でしょう)。

 マラソン系のコンテストでは、大体いつも、考察パズル部分ではっきり負けていた……とコンテスト後に分からされているので、もっとここに力を注ぐべきですね。