ABC200

ABC200に挑戦(もう結構時間たってしまいましたが)。

記念すべき200回目ということで問題文にもやたら200が出てきましたね。というわけで自分もここでいい結果を残さなければ…と思ったのだが結果は惨敗。まさかのRatingが下がるという結果に。

原因はいろいろ考えられるのだが、とりあえず思いつくものを列挙していく。

A~Cにやや手間取ってしまった

今回はA~Cが灰レベルと非常に簡単な構成。10分以内で素早く回答したかったところだが、Cで一度WAを出してしまってペナルティ5分。これはかなり痛かった。

Dのプログラムがなぜか動かなかった

Dも水色初級なので解けるレベルだったし、アルゴリズムも普通に思いついたのだが、なぜかプログラムが思うように動かず…。まだ原因を調べていないので単なるポカミスか言語の仕様を十分に理解していなかったからなのかは不明だが。

列挙といっても原因はこの2つが全てですね。Dの原因は判明したら追記するつもり。

DPその3 少し苦戦中

30日経ったので毎日書くことはやめにして、ここからは何日かに一度まとめて投下していきます。まずは100選の方の進捗から。実はあまり進んでいなくてまだQ49とかで止まっているのだが、、。

45　AOJ 2199 - 差分パルス符号変調

ナップザックDP最後の問題。正直題材にあまり興味がそそられないのだがまあやるしかない。計算量的には全然いけるはずなのに初めTLE。おかしいな。結局細かくいじったらギリギリ通ったけど何かモヤっとする。unordered_mapを使っているのがいけないのかな、という気もするけれど、だからといって代わりになるものも思いつかない。(この件がきっかけで先のコンテナの記事を書いたのだけれど)

46　ALDS_10_B - 連鎖行列積

連鎖行列積。定番問題…なのかもしれないけれど初めてやった。初め区間DPではなくナップザックDPで解こうとして失敗して一度仕切り直し。結局そこからも20分くらいかかった。。というのも、vectorでいちいちtemplateの引数書くのめんどくさいから省いていたら、どうもtemplateの引数推論ってC++17からしか対応していないらしくて。ノーマルC++で実行して思いっきりCE出しましたはい。てか何でAOJってデフォルトのコンパイラC++なの？？

47　JOI 2015 本選 2 - ケーキの切り分け 2

諸事情によりまだ実装途中。また追記します。

48　AOJ 1611 ダルマ落とし

場合分けするとゴチャゴチャするからあまりしたくないのだが、これはどうしても必要なパターン。想定解は[tex:O(N³)]なんだけど、初め書いたコードは[tex:O(N⁴)]時間だったので、解説を見てからもう一度書き直し。2回目はわりときれいにコードが書けた。AOJって公式の解説がないからいちいちググらなくちゃいけないのが少しめんどいなあ。

49　DPL_2_A - 巡回セールスマン問題

世にも有名なTSP。いつか高速な解法を見つけてみたいなあ、と夢があるけれど、まずはこの問題を解けなければ話にならない。bitDPの一問目。すべての頂点は一度ずつしか通らないので通ったかどうかをbitで記録できるのだが、そこを見落としてstart=goalの状態で探索してバグって時間がかかってしまった。もったいない。

50~はまたある程度進んだら書きます。

【30日目】1カ月経ったよ

「1カ月だけ頑張ってみよう！！」と言ってから一カ月経ちました。早いねー

というわけで1カ月を振り返ってみよう。

1カ月で水色に、、は当然無理でしたが(そもそもRatingの上がり方に限度がある)、実質目標達成といってもいいと思います。というのも、ここ2回連続で1200(水色下限)を大幅に上回るパフォを出しているから。しかも2回とも過去最高。おそらくこの調子で得点を重ねれば、あと数回のうちには水色になれるんじゃないのかな？と思っている。まあそのためにはまだまだコンテストに出続けなければいけないんだけど。

高いパフォを出せている要因としては、なんといっても

解ける問題を確実に高速に解けるようになった

ということが大きいと思う。AtCoderの場合部分点がないので、解けない問題は皆0点となり、結局解ける問題をどれだけ素早くこたえられたかでパフォーマンスが大きく左右される。特に前々回のようにD問題以降で急激に難度が上がるパターンの場合、これが顕著だった。

自分としては、良問100選を1問1問時間を計りながら解き進めることで、素早く実装する力がかなり身についたのではないかと思っている。

あと高速化に大きく寄与したのが

TLEやWAを出すことが減った

こともかなり大きい。以前はC問題程度でも一発でバグなく動くことはまずなかったのだが、最近では少し時間がかかるような問題でも一発でACできるようになった(提出前の修正もなく！)。バグの修正って一度沼にはまるとなかなか抜け出せないので、このことはかなり大きかったと思っている。

あと仮にバグがあったとしても、それを見つけ出す力もかなり身についたと思っている。直感で分かるようになってきたというか。

---

今後も続けられる限りこのブログは続けていこうと思います。

目指せ水色Coder!

【29日目】C++のSTLコンテナを比較してみる

何回か、計算量的にはOKのはずの問題で用いたコンテナの問題でTLEになったことがあったので、各コンテナの機能、実行時間等についてまとめてみた。

vector

一番よく使うやつ。push_backは遅いとか言われるけれど、試した限りは十分高速だったし、基本はこれでいい気がする。固定長の時は配列やarrayの方が高速でよいのかもしれないが、それが原因でTLEになることはなかろうからこれでよい気がする。面倒くさいし

unordered(multi)set, unordered(multi)map

ハッシュテーブル。ランダムアクセスが定数時間でできるのが特徴。ただデメリットも多い。まず遅い。10⁷要素くらい挿入で普通にTLEする。TLEもこいつのせいでなった。あとpair型のようにhash化不可能な型では使えない。あと調べたところによると、ハッシュ値が衝突すると実行スピードが大幅に落ちるらしい。いろいろとダメじゃん。

(multi)set

平衡二分探索木。以前は勝手にソートしてくれて便利、、と思っていたが、どうもハッシュテーブルに負けず遅いらしいと判明した。vectorに挿入してからソートした方が10倍くらい速い。意味わからない。それを知って以来使わなくなった。ただ、クエリ課題とかでいちいちソートしなくちゃいけないときには便利だと思います。

deque

これ便利。大好き。なんて言ったってstackとqueueの役割を両方同時にしてくれるんだもの。速度的にも問題ない。逆に単体のstack, queueってまず使う意味ない。

結論

基本は全部vectorでよい気がする。ハッシュテーブルと平衡二分探索木はやめた方が良い。ここに書いたの以外にもlistとかpriority_queueとかあるけれどまず使ったことないなあ。

【28日目】DP2日目

昨日の続きのDP。結構似たような問題が続く。

40　JOI 2012 予選 4 - パスタ

i日目までの場合の数は直近二日間(9通りの場合分け)にのみ依存することから漸化式を立てられる。条件が複雑なので実装がやや面倒くさかった。こういうのもっと手早く実装できるようになるといいな。

41　JOI 2013 予選 4 - 暑い日々

前問と似ている。というかJOIの全部似ている。こちらは前日にのみ依存するので実装は簡単。DPっていつも初期値をどうすればよいかで結構考え込んでしまう。。

42　JOI 2015 予選 4 - シルクロード

そろそろ飽きてきたJOI4問目。今までのDPの問題でフィボナッチの次に簡単な気がしている。JOIの問題ってAtCoderとかに比べると、全体的に問題設定が複雑なものが多い気がする。正直あまり好きではない

43　パ研杯2019 D - パ研軍旗

これも左の列から愚直にやっていけばよい。

44　AOJ 1167 - ポロック予想

最初に1~10⁶まで全部計算する方針で。途中何回か方針を変えたせいで時間がかかってしまった。ひょっとしたらTLEするかな…？と思ったけれど大丈夫だった。TLEしそうかな、と思ってもやってみるといけることって意外と多い。まあ採点機が優秀なんだろうな。

【27日目】今日からDP

良問100選もやっと3分の1まで来た。まだまだ先は長いが気を引き締めて頑張らねば。

今日からしばらく(No. 34 ~ 52)動的計画法(DP)が続く。これはグラフの次に苦手なのでしっかり押さえておきたい。。グラフと違って好きなのは好きなのだが、どう置けばよいのか分からずいつも苦戦する。

まずは基本から。

34　ALDS_10_A - フィボナッチ数

これはさすがにできる。

35　DPL_1_B - 0,1ナップザック問題

超定番ナップザック。もう何度もやっているので流石にこれもできるが、一から独力で思いつくか、と言われると何とも自信ない(え)。

36　DPL_1_C - ナップザック問題

ちょっと一捻りしたナップザック。この時点で若干苦戦気味(やばいね)。漸化式を少し変えないとTLEになる。式とにらめっこして計算の無駄を探して、という作業。

37　DPL_1_A - コイン問題　基本問題です。

ナップザックの亜種。これもできる。

38　ALDS_10_C - 最長共通部分列

LCS。最初は漸化式見ても何でそれでいいのか今一つピンとこなかったけれど、もうそろそろ慣れた。

今日39の途中までやったので、明日はその続きから。DPは漸化式さえ思いつけば実装はそこまで難しくないから頑張っていこう。

【26日目】ZONeエナジープロコン

昨日ZONeエナジープロコンに参加したのでそのことについて。

結果

以下の通り。 二連続水パフォ。やったね！！

もう少しで青パフォ行きそう。思ったよりも伸びてびっくりした。のちに詳述するが、やはりC問題ができたことが大きかったか。順位も初めて3桁入りした。

あと3回くらい水パフォ取り続ければ水色なれるのかな？そう思うと現実的な気がしてきた。頑張ろう！

各問題の所感

A - UFO襲来, B - 友好の印

特に問題なく。Bはいつもに比べると少し難しめかな？という気もしたけれど。立式に手間取って少し時間がかかってしまった。

C - MAD TEAM

Cだけど400点問題。最大値の最小値の最大値を求める。まあ二分探索(総合力F以上になる組み方の有無を調べる)だろうなーというところまでは簡単に思いついたけれどそこでいったん詰まった。その後少し見方を変えれば各Fについて全探索で調べられると気づいて実装。実装も割と重めだったのでそもそも時間内に終わるか微妙だったし、できたとしても一発ACは無理だろうな―と思っていたらあっさり一発で動いた。意外と力がついていることに驚いた。この問題ができたのは我ながら上出来だったと思う。

D - 宇宙人からのメッセージ

300点問題。この前やった何かの問題に似ているような。Rの回数を記録しておいて後でまとめて処理すればOK。ABDで18分かかった。もう少し早くできれば理想だった気はする。

E - 潜入

グラフ問題。これもまた以前似たような問題を見た気がしているのだが…。でも分からなくて諦めた。グラフは100問の方でも未修だし仕方がない。これから練習していこう。

難易度について

ちなみに今朝の時点ではまだ難易度がAtcoder Problemsの方で公表されていなかったので、自分で予想してみた。現在のレベル把握の参考になればと思い。

問題	予想	結果
A	灰初級	灰初級
B	灰中~上級	灰初~中級
C	水中級	水中~上級
D	茶上級	茶上級
E	水上級	青初級

Fは取り組んでいないので省略。我ながら結構当たっているが、CとEは思ったより難度高かったんだなーという印象。まあそれだけ自分のレベルが上がっているということですな。

今日はもう一つ投稿するかも。