あさかつ09/09 各地点に紐づく情報を配列で持っておく

 09/09
1. 北か南のどちらかがあるならどちらもないといけない。東と西も同様。
2. 前解いたやつ
3. WA. 解説読んだがその通りに実装したつもりだったのだが・・・TLEもあった。コードがバグってたのはそれとして（問題としてはそっちが本質な気もするが）、遅かった処理が何か？
#あさかつ考察

他の人の回答例を読んでいた。ループができたかどうかを判定する処理を、（私は今まで訪れた地点を順に配列に持ったうえで）配列の中にその要素があるかどうかで判定していたのに対して、各地点に対して訪れたかどうかを配列で持っておいて、ある地点にたどり着いたら配列の特定の要素を見て

訪れたかどうかを判定していた。おそらく自分が書いたコードで配列のnot inとか使って判定していたのがO(N)で重かったんだろうな・・・あくまで予想だが　まあ今日もD問チャレンジできたのでよいということで。シンプルだったから解きたかったが。

atcoder.jp

この回答では、ある地点に訪れていないときは-1,訪れた時は何回目に訪れたかを記録している。個人的に見通し良く解けそうな解き方だと思って参考にさせていただいた。

 

あさかつ09/08　５問目に挑戦

 09/08
1. S.replace("HAGIYA", "HAGIXILE")
2. 各行の差がすべて一定＋各列の差がすべて一定解説もチラ見したけど似たようなものだろ
3. Counterゲーム。各ボールの種類を降順に並べて、K番目以降の要素の和
4. 幅優先探索。最近勉強したので調べながらもちゃんと書けて良かった。
#あさかつ考察

5. WA.いろいろ考えて辺りを付けて実装したけど、そのアイディア自体が間違って居たっぽかった。k個の部分集合を選ぶならサイズがk-1、要素数の合計がk(k-1)/2になりそうなところまでは結果的には合っていたが・・・うーん
そのうち解説放送でも見ようかな。

ひとまず、５番までしっかり考察できたのはよし。

５番の自分の解法がなぜ間違っているか良く分からないな。

割り振り方→こんな感じ

１　３　　６　　　10

１２　　５　　　９

　２３４　　　８

　　　４５６７

　　　　　　７８９10

 あとで解説放送でも見るか・・・
解説放送なかった・・

Level 4:
解説放送なかった・・・

あさかつ09/05 最近実装めんどくさい系にやられてる件について

 まあ、実装めんどくさい問題にも果敢に立ち向かえるようになってきたのはいいこと（以前はめんどくさい問題にたどり着けもしなかったので）

あさかつ09/03 StrawberryCakesが難しかったので詳しい考察は今度

 

あさかつ09/02 単純なBFSは秒で書きたい

 09/02
1. 単純な分岐
2. すべての場合を探索してOK
3. 大きさ的に隣の座標との距離を取る。距離の大きいところから順にN-1個仕切りを置いてその仕切りの間を一個のマスで移動させることを考える。そうすれば答えは距離の小さい方から順にM-N or 0 個
配列の扱いをバグらせて1WA
#あさかつ考察

 

4. おしい、一分半おくれでAC. BFSで最短距離を調べる。(迷路の.の数)-(最短距離)が答え。
BFSの実装をもっとスムーズにできるようになれたらよい。まあでもD問題にあと少しで手が届きそうだったので良し。

 

BFS（とかDFS）の書き方にもっと慣れて、あとライブラリ(deque)の使い方にももっと慣れたらスムーズに解けるだろう　そのうち応用もできるようになるだろう。

つぎは4問目まで時間内に解き切りたい。

あさかつ09/01 文字列の足し算->dequeでTLEがACになった

 09/01
1. 最近解いた。寝ぼけていてWAしてしまった。
2. Nの約数aを求めてa+N//aの最小値を求める
3. TLE. 一度馬鹿正直に解く→TLE. 文字列反転が重そうだと気づき、反転しているかの情報を-1or1で持っておく。多分解説の通りに解いたと思ったんだが。dequeを使えばよいか？

超適当に文字列の足し算だからそんなに重くならなくね？とか思っていたのだが・・・

4. deque使ったらACできた。
https://docs.python.org/ja/3/library/collections.html#deque-objects
にはlistのpopがO(n)になるようなことが書かれているが、たぶんpythonの文字列もまあリストのようなものであって、文字列の先頭や末尾に文字を足すことも同様にO(n)なのかな・・・？どなたか詳しい方教えてください.
#あさかつ考察

 

制約きつそうだと思ったらとっととdeque使うのがよさそうか。

このあたり「どういう処理が重いのか」あんまり良く分かってないな。

あさかつ08/31　整数に関連する問題の扱い方、計算量を考える

 08/31
1. AとBの間にCがあるかどうか
2. 前やった
3. レートが高いものを上からK個取ってきて、その中からレートが小さい順にみていく。
4. ???

4の解説を読んだ。なるほど。とりあえずn,h,w全部のループだとだめだということは考えた。そのあとはなんかNが四の倍数の場合？とかうまく決め打てないかと謎の式変形ばかりをしていて、二重ループとかそういう方向に頭がいかなかった。今解いてるのは算数の整数問題じゃなくてプログラムの問題だぞ

整数チックな問題だと嬉々として式をごちゃごちゃし始めるの完全に算数

atcoder.jp/contests/tenka1-2017/submissions/16413115
pythonだとTLE, pypy3だと通った。

整数かどうかを判定するのにis_integerなぞ良く分からない関数を使ってしまったが、a%b==0で良かった

 

アルゴリズムというかプログラムの問題として解くことを考えよう。