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

30日経ったので毎日書くことはやめにして、ここからは何日かに一度まとめて投下していきます。まずは100選の方の進捗から。実はあまり進んでいなくてまだQ49とかで止まっているのだが、、。 45 AOJ 2199 - 差分パルス符号変調 ナップザックDP最後の問題。正…

「1カ月だけ頑張ってみよう！！」と言ってから一カ月経ちました。早いねー というわけで1カ月を振り返ってみよう。 1カ月で水色に、、は当然無理でしたが(そもそもRatingの上がり方に限度がある)、実質目標達成といってもいいと思います。というのも、ここ2…

何回か、計算量的にはOKのはずの問題で用いたコンテナの問題でTLEになったことがあったので、各コンテナの機能、実行時間等についてまとめてみた。 vector 一番よく使うやつ。push_backは遅いとか言われるけれど、試した限りは十分高速だったし、基本はこれ…

昨日の続きのDP。結構似たような問題が続く。 40 JOI 2012 予選 4 - パスタ i日目までの場合の数は直近二日間(9通りの場合分け)にのみ依存することから漸化式を立てられる。条件が複雑なので実装がやや面倒くさかった。こういうのもっと手早く実装できるよう…

良問100選もやっと3分の1まで来た。まだまだ先は長いが気を引き締めて頑張らねば。 今日からしばらく(No. 34 ~ 52)動的計画法(DP)が続く。これはグラフの次に苦手なのでしっかり押さえておきたい。。グラフと違って好きなのは好きなのだが、どう置けばよいの…

昨日ZONeエナジープロコンに参加したのでそのことについて。 結果 以下の通り。 二連続水パフォ。やったね！！ もう少しで青パフォ行きそう。思ったよりも伸びてびっくりした。のちに詳述するが、やはりC問題ができたことが大きかったか。順位も初めて3桁入…

まずは昨日の続きから。 31 JOI 2012 予選 5 - イルミネーション 結局合計で50分くらいかかったorz コンピュータの場合、座標を扱うときに(入出力の都合上)xとyを逆転させた方が楽(a[y][x]の形にする)だからその方式で実装していたのだが、それで途中から混…

今日は幅優先探索。まだ途中なので続きは明日。 28 ALDS_11_C - 幅優先探索 毎度おなじみALDS。これはサクッと解けた。 29 AtCoder Beginner Contest 007 C - 幅優先探索 この問題前もやったんだけど、まあいいや、もう一度やった。グリッドを移動する系の問…

最近忙しくてあまりできていなかったのだが今日はやります。深さ優先探索(Depth First Search)。正直DFSは何というか単純すぎてあまり好きではないのだが。全4問、順に所感を書いていきます。 24 ALDS_11_B - 深さ優先探索 ALDSの問題は基本アルゴリズムの実…

昨日の分です。最近遅れ気味なのは反省してます。。 先日 23 JOI 2008 本選 3 - ダーツ でなぜかTLEになった問題。結局コンテナとしてsetを使っていたのをvectorに直したら制限時間内に計算できたのだが、そこで コンテナ毎に実行時間にはどの程度差があるの…

昨日から二分探索に取り掛かっていたのだが記録していなかったので、併せて書いておく。23だけはまだ途中。 18 ALDS_4_B - 二分探索 upper_boundを使えば一発。時間制限が厳しければ他の方法を取るけれどここはそれで十分。 19 JOI 2009 本選 2 - ピザ 本店…

昨日書いたのに投稿し忘れましたorz 以下原文ママ↓ 昨晩のABC199の結果、ついに！ 緑Coderになることができました！ やったね！！ そして水パフォ！これもうれしい。最近力がついてきていた実感があったのでそれが確かめられてよかった。 具体的な回答状況は…

昨日大苦戦したnext_combinationは結局諦めて他の人のコードを写した。もう少し力をつけてからまた見返してみることとする。 今日はまた一昨日の続きに戻る。Q14~17にトライ。 14 Square869120Contest #4 B - Buildings are Colorful! 早速上記のnext_combin…

昨日の流れからいくと今日は14. Square869120Contest #4 B - Buildings are Colorful!からという話になるのだが、これを実装するのにあたり配列を並べ替えて全通りのcombinationを列挙することができたら楽ではないか？？と思い、next_combination関数の実装…

昨日ノーマル全探索を終えたので今日はbit全探索を。bitを用いた実装は初めのころは「ここは&だっけ|だっけ？」みたいな感じで大分手間取った記憶があるのだが、その点かなり慣れてスムーズにできるようになってきた気がする。でもまだ典型的なもの以外は少…

今日は6~9を。昨日の分よりはやや難易度が上がったが、この程度ならまだまだいける。 ただもう少し早くできたら理想かな、という気もする。結構添字とかで「あれここはa[i]だっけ？a[i+1]だっけ？」とかなってタイムロスをしている感。あとはループの範囲と…

昨日見つけたこちらの記事。 qiita.com 水coderになるためにはとにかく演習！ということや、そのためには片っ端からというよりは選ばれた良問をやった方が良い、ということが分かってきたので、この記事に出ていた良問100選を順にやっていくことにした。 と…

本日二つ目の投稿。二つやると結構大変だけど昨日忘れた自分が悪いですねはい() 一言で言えばこんな記事を見つけましたと言う話。 qiita.com 初級編〜上級編とあるが、現在茶コーダーで水を目指す自分として役に立ちそうなのはこれ。具体的に何をやったら良…

昨日書き忘れましたねはい。ので今日二日分書きます。 まずは先日の最強学生プログラマー選手権(だっけ？)のE,F問題を軽く振り返って。まずF問題は座標圧縮が必要になってきそうなので明日学習しようと思う。ちょうど良さげな問題も見つけた。 atcoder.jp ん…

タイトル通り。実は予定があって17:30までしか参加できないのでかなり迷ったのだが…。参加を決めた理由としては、まあこれが原因でRatingが下がるということはないだろう、というのと、単に一刻も早く力試しがしたかったのと。結果はご覧の通り。 短い時間で…

結論から言うと忙しかったので今日はほとんど進められていない。。ABC197-Fに取り組んだがWAになり、原因不明のまま。そろそろ自力は限界なので、他の人のコードを読んでいい所を盗む形でやりたい。 3分の1(10日間)ちょうど経過したので、少し今までを振り返…

昨日の続きということで、今日はEとF問題。これらは完全にアルゴリズムを思いつかず解けなかった。どういう発想が必要だったのか考察してみる。 E - Traveler 「同じ色のボールをどういう順番でとるかがカギだな」「各色について、取り方は高々2通りしかない…

昨日ABC198は一通り復習し終えたので、今日は1つ前のABC197に取り組んでみる。残念ながら100分というまとまった時間は取れなかったので、時間は正確にははかっていないが、多分100分以内に4完したと思う。EとFはまだ途中なので、CとDを先に振り返っておこう…

一昨日大敗したABC198について、昨日は全体的な課題点を考察したが、今日は個別の問題について見ていく。Fは今のレベルではかなり無謀な問題なので、大きな敗因だったDとEの失敗について。 D - Send More Money atcoder.jp 覆面算の問題。これに関しては解け…

昨晩ABC198に参加した。今日新Ratingが出たが、結果は火を見るより明らか。 死にました。 具体的にはこのような結果に。 まさかの3完どまり、パフォも過去最低、という惨敗ぶり。5完目標にしてこれとは情けない限り。悲しんでいても埒が明かないので、以下反…

まずは昨日の復習の続き。 D - I Wanna Win The Game atcoder.jp (本題とは逸れるが、このタイトルはどういう意味が込められているのだろうか…？深い意味があるのかはたまた何の意味もないのか。) 出ましたXOR。苦手なんだよな、、と思いつつも成り立つ性質…

最初はABCをやろうと思っていたのだが、時間もあるのでARCにチャレンジしてみた。 結果はご覧の通り。 400点問題と500点問題の間の壁はやはり高かった。A,Bは(若干苦戦しつつも)解けたが、C,Dは全く歯が立たず、途中でギブアップ。以下解説を見て再考。 C - …

今日は時間がなくてあまりできていないのだが、尺取り法の復習だけ少し。 尺取り法 (two pointers technique) 個人的にはtwo pointersというネーミングの方が分かりやすい感。条件を満たすような最長の区間[l, r)を求めるにあたり、lとrのうち片方を固定、片…

昨日のE問題 E - Transformable Teacher を再考するため、以下の記事を読んで参考にしてみた。 rsk0315.hatenablog.com いくつか学んだことを↓ 累積和はs[0]=0とする これは早速このE問題で使えた。半開区間をベースに考える、という発想らしい(s[0] = [0, 0…