【18日目】next_combinationの実装を試みる
昨日の流れからいくと今日は14. Square869120Contest #4 B - Buildings are Colorful!からという話になるのだが、これを実装するのにあたり配列を並べ替えて全通りのcombinationを列挙することができたら楽ではないか？？と思い、next_combination関数の実装を試みた。
想定としては、 * 基本的な用法はnext_permutationと同じ。ただし、組み合わせの個数kを引数に取る * 順番を入れ替えたものは同じとみなし、組み合わせの中で順番が昇順になっているもののみを返す * 残りの部分は昇順にソートしておく(実装の都合上)。 といった具合。
この辺りの記事を参考にして作ろうとしたが…
結論から言うとまだ上手くいっていない。なるべくコード丸写しではなく自分の頭で考えて実装しようとしたのだが、なかなか思うようにいかない。これ以上のタイムロスもしたくないので、そろそろ上記のコードを写しながら考察する方針に切り替えようと思う。
明日は
ABC199
ですね！今度こそ5冠を目指す！そろそろ緑入りしたいな〜
【17日目】bit全探索
昨日ノーマル全探索を終えたので今日はbit全探索を。bitを用いた実装は初めのころは「ここは&だっけ|だっけ？」みたいな感じで大分手間取った記憶があるのだが、その点かなり慣れてスムーズにできるようになってきた気がする。でもまだ典型的なもの以外は少し手間取るかも。
10 ALDS_5_A - 総当たり
基本問題。特に問題なし。ここまで(恐らく)WAやTLEを一つも出さずにクリアしているのは我ながら上出来だと思う。
11 AtCoder Beginner Contest 128 C - Switches
これも問題条件にこそ一捻りあるが実装は単純。bitの扱いの練習になる良問だと思う。
12 AtCoder Beginner Contest 002 D - 派閥
人間関係を隣接行列(bit)形式で保持しておくことで実装できる。bitで表された二つの集合s,tについて、s ∈ t ⇒ (s & t) == sであることは押さえておきたい。あと左の式で、&の方が==より優先順位が低いことを知らずに手間取ってしまった。優先順位はしっかり頭に入れておかないと。あと原因不明のバグがあったら原因の一つとして疑ってみよう。
13 JOI 2008 予選 5 - おせんべい
難しめって書いてあった割には割とできた。制約条件の偏りが鍵になってくる系の問題。
【16日目】良問100選の続き
今日は6~9を。昨日の分よりはやや難易度が上がったが、この程度ならまだまだいける。
ただもう少し早くできたら理想かな、という気もする。結構添字とかで「あれここはa[i]だっけ？a[i+1]だっけ？」とかなってタイムロスをしている感。あとはループの範囲とかでも同様。対策としては、以前書いた「半開区間を基本とする」というのもそうだし、あとはやはり慣れなのか。
以下一問ごとの感想。
6 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
「Sからどの3つを選ぶか」から「000~999の各値について、Sから作れるか」という視点に切り替えることがポイント。この手の切り替え結構苦手なんだよな…。このくらいだとできるけど。
7 JOI 2007 本選 3 - 最古の遺跡
正方形は、隣接する2頂点さえ選べば2つにまで絞れるということがポイント。数学的な考察なので割とできた。あとこの問題を解くに当たって特定の座標の点が存在するかを高速に検索する必要があったので、operator<, ==を使える座標保持クラスPtを用意した。これ結構汎用的に使えそうなので取っておく。早速9でも使った。
8 Square869120Contest #6 B - AtCoder Markets
これ面白かったな。コード書く前の考察が大事になってくる系の問題は割と好き。これの場合、ルートなどというものはいちいち考えなくとも、入口とマスAの距離、出口とマスBの距離さえ考えれば良いということ、さらに、移動時間の合計は一次関数の絶対値の和で表されるということがポイント。つまり絶対値記号の中身の符号が変わるポイント(入口、出口がA,Bと重なるポイント)のみ考えれば良いわけだ。面白い。
9 JOI 2008 予選 4 - 星座探し
7番とよく似ている。というか7できればこれはできる。特筆事項なし。
明日はbit全探索から。
【15日目】先日の記事の良問100選を早速やってみる
昨日見つけたこちらの記事。
水coderになるためにはとにかく演習！ということや、そのためには片っ端からというよりは選ばれた良問をやった方が良い、ということが分かってきたので、この記事に出ていた良問100選を順にやっていくことにした。
というわけで早速それ用のcppファイルを100個まとめて量産↓
全部は見せませんが大体こんな感じで100個。分野ごとに偏らないように進めるべきかとも少し迷ったが、複雑なことをしても後でわけわからなくなりそうなので、とりあえず1番から順に解いていくこととする。
今日は6番まで。ここら辺は全探索なので割とサクサク進む。この調子で明日も進めていこう。
【14日目②】便利なサイトをいくつか見つけたので
本日二つ目の投稿。二つやると結構大変だけど昨日忘れた自分が悪いですねはい()
一言で言えばこんな記事を見つけましたと言う話。
初級編〜上級編とあるが、現在茶コーダーで水を目指す自分として役に立ちそうなのはこれ。具体的に何をやったら良いか、どのくらいのレベルになれば水色になれるかが非常に具体的に書いてあり、今後の方針が立てやすい。
いくつか読んでわかったことを↓
ここに書いてある水色になるために抑えるべきSTLの機能、アルゴリズムは9割方習得したものである。ということはそれらを運用する力がまだまだ足りていないということ。恐らくここから水色までは、新たなアルゴリズムを学ぶよりはとにかく片っ端から問題を解いて実践力をつけていったほうが得策。
具体的にどのくらい解ければいいのかについては、以下のような記述があった。
AtCoder Beginner Contest で確率 8 割以上で 4 問正解できる
AtCoder Beginner Contest で確率 3-4 割で 5 問正解できる
AtCoder Beginner Contest の問題をある程度早く解くことができる
自分は今の感覚だと4完7割、5完1割という感じなので、そこまで水色から遠い位置にいるわけでもなさそう。ただここの差がかなり大きそうな印象は受ける。だからといって、特定の何かが致命的にダメというわけでもないので、やはり全体的に慣れが足りないのだと思う。
だからといってどんな問題から解いていいのか分からない、、という私みたいな人のために、良問100選が書いてあった。とりあえずはそれをこなしてみようかな。
【14日目①】解説のコードを読んでみて気づいたこと
昨日書き忘れましたねはい。ので今日二日分書きます。
まずは先日の最強学生プログラマー選手権(だっけ？)のE,F問題を軽く振り返って。まずF問題は座標圧縮が必要になってきそうなので明日学習しようと思う。ちょうど良さげな問題も見つけた。
んで問題のE。解説読んだ時からこりゃ実装がえらい難しそうだな…と思ったのだが、案の定自力での実装は難しかったので、解説のところにあった解答コードを読み解いて学習することにした。確か黄レベルだったと思うから今の段階で自力で解ける必要も必ずしもないと思っているし(まずは水レベル以下を確実に解けるようにしたい)。
そこでいくつか気づいたことを↓
問題自体について
「折りたたむ」って文字通りSを折りたたんでいるのか。折りたたみつつ各文字の出現頻度を加算していく。自分は折り畳まずに各ユニットの先頭要素の位置と長さを記録しておいて後からSをたどって出現文字を加算していこう、としたから実装できなかったのか。
正直これを自力で実装できる自信は全くない()
実装について
valarray, partial_sortは存在を知らなかった。iotaは前やったけど存在忘れてた。今度から使えそうなら使っていこう
先頭、末尾からコンテナの要素を参照するのに、先頭からの時は順に[]演算子でアクセスしているのに対し、末尾からのときは一要素ずつpopしながらback()でアクセスしているのは何か意味があるのか？そのほうが高速なのか？
結構こうやって熟練者のコードを読むのも勉強になるなと思った。これからも少しずつ取り入れていこうと思う。
【12日目】第二回日本最強プログラマー学生選手権に参加！
タイトル通り。実は予定があって17:30までしか参加できないのでかなり迷ったのだが…。参加を決めた理由としては、まあこれが原因でRatingが下がるということはないだろう、というのと、単に一刻も早く力試しがしたかったのと。結果はご覧の通り。
短い時間で解かなくてはならなかったのは痛手だが、Atcoder Problemsで見る限りE以降は一気に難易度が跳ね上がっているようだし(解いていないので何とも言い難いが)、そう思うと時間があったとしても4完が限界だったのかもしれない。
Dまでは割と簡単めだった(茶以下)が、それ相応に解けたと思うので良かったと思う。
以下は具体的に各問題を振り返って。記載のないA,C問題については特に問題がなかったと思う。
B - Xor of Sequences
これ数列の各要素の値が小さいから、二つの数列それぞれに含まれる値の要素をbitsetの形で表現してXORとれば良いんだよね…と終わってから気づいた。馬鹿すぎる。無駄に時間がかかってしまった。B問題だからといって油断せずに、制約条件が緩くなっているところはないかよく確認しよう。
D - Nowhere P
最初DPでやろうとしてサンプルケースでTLEなった。制約条件はよく確認しよう。そこから少し考えて(N,Pが小さい場合で実際にやってみて)漸化式立てなくてもと言う式で一発で解けるね、と気がついた。いつもこうやって難しく考えすぎてしまうんだけど、問題を見たら
1に一つの立式で(要はO(1)で)解けないか検討
2に全探索でTLEならないか検討
3で初めて他の手法を考える
というのは教訓としておさえておきたい。
