茶coderが1カ月だけ競プロをガチってみる

1カ月でどこまでいけるか。

【25日目】幅優先探索その２

まずは昨日の続きから。

31　JOI 2012 予選 5 - イルミネーション

結局合計で50分くらいかかったorz コンピュータの場合、座標を扱うときに(入出力の都合上)xとyを逆転させた方が楽(a[y][x]の形にする)だからその方式で実装していたのだが、それで途中から混乱してきてすごく手間取ってしまった。自分で混乱しないように変数名工夫するなり何かした方が良いかもしれないな。普段の問題だと基本的にxとyが入れ替わっても支障はないのだが、この問題は6角形の敷き詰めなので、xとyが入れ替わると答えが出ないのがネック。

32　AOJ 1166 - 迷図と命ず

入力方式が独特なのでその処理が少し大変だが、そこを乗り切ればごくごく普通の迷路。xとyの逆転問題は上ので慣れた後だったので、多少は手早くできた。24分。このくらいのを15分くらいで実装できればもっといいんだけどなあ。

33　AtCoder Beginner Contest 088 D - Grid Repainting

これも問題文がややこしく書いてあるだけで実態は普通の迷路問題。最初問題条件を読み間違えて少し手間取ったがその後は順調にできた。16分。

夜はまたコンテスト。感想は例によって明日投稿する所存。

【24日目】幅優先探索その１

今日は幅優先探索。まだ途中なので続きは明日。

28　ALDS_11_C - 幅優先探索

毎度おなじみALDS。これはサクッと解けた。

29　AtCoder Beginner Contest 007 C - 幅優先探索

この問題前もやったんだけど、まあいいや、もう一度やった。グリッドを移動する系の問題って配列外参照の判定をいちいちしなくてはならないの面倒くさいんだけど、この問題の場合周りが壁だからその心配がなくて楽。逆に普段からこういう実装にすればバグが減らせるのかな？

30　JOI 2011 予選 5 - チーズ

わざと問題は回りくどく書いてあるけれど、結局のところは工場i~i+1間の道のりを順々にBFSで調べていけばよいだけの話。楽勝楽勝…と思っていたら配列外参照で思いっきり(手元で)REしたorz 大体REの9割くらいが配列外参照でやらかしている感あるから、いい加減気をつけねばとは思っているのだが。。

31　JOI 2012 予選 5 - イルミネーション

実装重めって書いてあったけど確かに重い。30分以上かかってまだできてないorz 時間計算量O(HW)だから実装できればTLEにはならないと思うんだけど。。また明日続きをやる。

明日はまたコンテストデー。
ZONeエナジー プログラミングコンテスト “HELLO SPACE”
かな。(ABCではないんだね。何が違うのだろう)

目標は相変わらず5完で。でも難易度にもかなり依存するから、水パフォでればよいかな、とは思っている。これが30日経過前最後のコンテストになるから、ここでいい結果を出しておきたいなあ。

【23日目】深さ優先探索

最近忙しくてあまりできていなかったのだが今日はやります。深さ優先探索(Depth First Search)。正直DFSは何というか単純すぎてあまり好きではないのだが。全4問、順に所感を書いていきます。

24　ALDS_11_B - 深さ優先探索

ALDSの問題は基本アルゴリズムの実装がきちんとできているか確認するのに非常に便利やね。ちなみに問題条件勘違いしてWAくらって若干手間どった。。

25　AOJ 1160 - 島はいくつある？

前Atcoderの方にも似た問題があったような。。典型なのかな。探索した島を消していくことで重複なくできる。

26　AtCoder Beginner Contest 138 D - Ki

(問題の英語名なぜTreeでなくKiなのか。。)与えられた頂点にだけxを加算しておいて、最後に一気にDFSで累積和を出せば解ける。クエリ系ではよくあるパターン。

27　JOI 2009 予選 4 - 薄氷渡り

25番と似ている。違いは探索終了後薄氷を復元しなくてはいけないことくらいかな。

あと、これはDFS全般についてだが、頂点がすでに通ったことがあるかどうかの判定は、再帰関数のforループ内ではなく、再帰呼び出し後の冒頭で行った方が良い気がする(そうしないと24、27のように始点を固定しないパターンに対応しづらい)。

特に問題なかったので次はBFS。これ終わったらやっと単純探索は終わりだーー

【22日目】コンテナ毎の速度の違いについて

昨日の分です。最近遅れ気味なのは反省してます。。

先日

23　JOI 2008 本選 3 - ダーツ

でなぜかTLEになった問題。結局コンテナとしてsetを使っていたのをvectorに直したら制限時間内に計算できたのだが、そこで

コンテナ毎に実行時間にはどの程度差があるのか？

ということを疑問に思い、調べてみた。

具体的には、 * 各コンテナ(vector, set, multiset)に106個の値を昇順に格納する * vectorの場合は格納してからソートする ということをやってその実行時間をclock関数で計測。コンパイラはGCC。

コードは以下の通り。

    start = clock();
    vector<int> a(N);
    for(int i=0; i<N; ++i) a[i] = s[i];
    sort(a.begin(), a.end());
    end = clock();
    cout << (double)(end - start)/CLOCKS_PER_SEC << " sec." << endl;
    start = clock();
    multiset<int> c;
    for(int i=0; i<N; ++i) c.insert(s[i]);
    end = clock();
    cout << (double)(end - start)/CLOCKS_PER_SEC << " sec." << endl;

setは省略。

結果…

  • vector -> 0.312 s
  • multiset -> 1.958 s
  • set -> 0.065 s

というわけでとりあえずmultisetはめちゃくちゃ遅いということは分かった。これはどのコンパイラでも大差なかったからこういうものなのだと思う。今度から使うのやめよ。。

一方、今回ネックとなっていたはずのsetはむしろかなり高速という結果に。他の操作(イテレータ走査、二分探索など)も試したが全く遅いということはなかった。じゃああのTLEの原因は何だったんだ？？真相は謎のままである。

【21日目】二分探索

昨日から二分探索に取り掛かっていたのだが記録していなかったので、併せて書いておく。23だけはまだ途中。

18　ALDS_4_B - 二分探索

upper_boundを使えば一発。時間制限が厳しければ他の方法を取るけれどここはそれで十分。

19　JOI 2009 本選 2 - ピザ

本店を店のリストの両端に入れれば愚直にできる。upper_boundとかlower_boundっていつも境界条件で少し考えてしまう。二分探索するリストにmax, minの値をあらかじめ入れておけば気にせずに済むのかな？

20　AtCoder Beginner Contest 077 C - Snuke Festival

3段というのがミソ。真ん中の段を基準に両側それぞれ二分探索する。

21　AtCoder Beginner Contest 023 D - 射撃王

出ました最大値を最小化する系の問題。この手の問題を二分探索で解けると知った時には感動したし、今でも一番好きなタイプの問題。18~20はupper/lower boundだけで書けたので、ここで初めてまともなbinary search書いた。以前知っためぐる式使ってみたけどやはり使いやすい。境界条件とかで実装少し手間取った。

22　AtCoder Regular Contest 054 B - ムーアの法則

連続的な二分探索。数学的な考察で解く問題。double型だと精度とか考えるの苦手で嫌なんだけどこの問題は特にそういう心配はいらなさそうだった。最後求めるものを間違えて無駄に手間取ってしまった。

23　JOI 2008 本選 3 - ダーツ

まだ途中。2本ずつに分けることで計算量O(N^{2}logN)で解こうとしたのだがTLE。N=1000なのに駄目なのか、それとも計算量の見積もりが間違っているのか。

【20日目】緑Coderになりました！！

昨日書いたのに投稿し忘れましたorz 以下原文ママ↓

昨晩のABC199の結果、ついに！

緑Coderになることができました！

やったね！！ f:id:danook:20210425145419p:plain そして水パフォ！これもうれしい。最近力がついてきていた実感があったのでそれが確かめられてよかった。

具体的な回答状況はこのような感じ。 f:id:danook:20210425151011p:plain

勝因としてはやはりA~Cを12分で高速回答できたことだと思う。今回のコンテストの場合D問題以降が難しく(青難度以上)正答が難しかったので、いかに前半3問を速く解けるかによってほとんど順位が決まっていたと思う。今までだとどんなに速くても3問に20~30分はかかっていたところなので、それを12分でできたことは我ながらよくやったと思っている。

A~Cは典型的な問題だったので特にコメントすることはない。D問題以降は、今やっている100題が終わってから再度取り組もうと思う。まだ該当部分(グラフなど)まで到達していないので。D問題の不正解率が異常に高いのが気になるなあ。

【19日目】全探索コンプリート！

昨日大苦戦したnext_combinationは結局諦めて他の人のコードを写した。もう少し力をつけてからまた見返してみることとする。

今日はまた一昨日の続きに戻る。Q14~17にトライ。

14　Square869120Contest #4 B - Buildings are Colorful!

早速上記のnext_combinationを用いて実装。bit全探索を前提にしている気もするけれどまあいいや。そこまで苦戦はしていない…けど10分くらいで解けるとなお良いかな。(14分かかった)

15　AtCoder Beginner Contest 145 C - Average Length

Nが小さいからO(N!)時間でも解けるんだけど、O(N2)時間でも解けそうだったのでそちらにトライした、、が苦戦した。各区間を何回重複して数えているか？などを考えていたら頭がこんがらがってしまった。だめだな。

16　AtCoder Beginner Contest 150 C - Count Order

next_permutationで一発クリア。知っていれば難しいところはない。

17　ALDS_13_A - 8 クイーン問題

端的に言ってしまえば、x, y, x+y, x-yがいずれも重複しないように8か所置けばよいわけだ。これ実装に苦戦するやつちゃうかな、、と思いきや案外あっさりAC。最近ある程度長いコードでもバグを作らずに書けることが増えてきた実感があってうれしい。

まもなくABC199が始まりますな。どうなることやら。考察は明日投稿しますね。