次はyukicoder No1と言ったな、あれは嘘だ。
007！
実は見たことがない。
ちょっと人生損している感じがするから見てみたいと結構前から思っている。

初めて同じコンテストを通して解いた。
全てACが出るまで3時間半くらいかかった。
ゲーム配信を眺めながら解いていたからまじめに頑張れば2時間半くらいだったかもしれない。
D問題は方針通り解いてWAしてから他人の回答を見たが、結局何の意味もなかったから実質1人で解き切ったと言っても良いだろう。
むしろ他人の答えと自分の回答の違いを見つけるのに時間を食ったので、他人の回答が見られない状況の方が早かったまである。


A 植木算
https://atcoder.jp/contests/abc007/submissions/3862921
B 辞書式順序
https://atcoder.jp/contests/abc007/submissions/3862989

この2つはまあ問題ない。
A問題はここまで典型的な植木算とは思わなくて衝撃を受けた。
B問題はちょっと無駄なことをしようとしてしまったのを反省。
bbbbb→aaaaaなんてしなくてもa以外ならaを出力すれば良いとすぐに気づくべきだった。
一種のいじわる問題と感じた。
ここまでで30分ほど。


C 幅優先探索
https://atcoder.jp/contests/abc007/submissions/3863401

一目見て「幅優先探索だ！」って思ったよね、書いてるんだもん。
1年前に水たまりがどうのっていう問題を解いたことがある気がするが、ある程度知識がついてから与えられた盤面に対して何かをする問題は初めてだった。
そもそもDP以外の探索問題は全探索以外やったことがないので、dxdyとかどうやって使うんだっけとかは少し調べたが、特に問題なく書けた。
ダイクストラ法を実装した経験が生きてキューを使った実装をかなりシンプルに書けた気がする。
1文字ずつ入力を受け取るにはどうしよう、という部分に一番時間を使った。
cin.ignore()使うのかなとか色々調べたが、char型に代入して行けばいらないらしい。
じゃあcinで改行をchar型に入れられないのか？
ひいては半角スペースも同じじゃないのか？
この辺りは要勉強。
ここまでで1時間15分ほど。
A,B,Cと3連続AC。
簡単な問題でもどこかしらミスをすることが多かったので、嬉しいと共に少し成長を感じた。


D 禁止された数字
WA
https://atcoder.jp/contests/abc007/submissions/3864683
AC
https://atcoder.jp/contests/abc007/submissions/3864750

問題のD問題
あまり調べていないがDPで解くのが主流っぽい？
0~9,0~99,0~999,...と分けた場合の4と9の数は関数で表せることをすぐに確認できたのでそれを使って解く方針にした。
当初下の桁から余りを使って数えていたが、それだと上位に4がある場合にうまくいかないことにほぼ完成してから気付いた。
1234567なんかの場合に、一番下の桁だけを考えた場合に0～7は直接4を含まないが、実際には1234560～1234567なので4を含むということだ。
上から順に書き換えるように直し終わってWAした時点で2時間半ほど。
ここからが分からなかった。
結論を言えばpow関数の誤差。
例えばこんなプログラムを書く。

今回は最新問題。
解き始めたのは当日だが参加はしていない。
性格上コンテストに参加するのはかなり先になりそう。

コード①
https://atcoder.jp/contests/caddi2018b/submissions/3853552
コード②
https://atcoder.jp/contests/caddi2018b/submissions/3853928
コード③
https://atcoder.jp/contests/caddi2018b/submissions/3853945




一応解説は軽く目を通したが、初見で思い浮かんだ解き方と同じで嬉しい気持ちに。
ただ解説の書き方が難しすぎて一瞬こんな問題解けねぇと思った。


コード①
今回の挑戦は素因数分解のプログラムを探すことから始まった。
普通に2で割れるだけ割って・・・ってやってたら遅いでしょさすがに？って思いながら調べてたらまさかのこれが正解だった。
入力値大きいしこれだとTLEだろうと2で割るのをやめて2のn乗3のn乗と割っていく関数を作成したものの、ところどころ間違えたりTLEだったり。
回答例見るとみんな普通に素因数分解してるしn乗しなくていいや。

コード②
間違いが全く分からない。
他人のコード見て間違い探しするも分からない。
for文で最終的な答えを求めているコードを発見。
試しにその方式で書いてみるとあっさりAC。
？？？？？
割り算で誤差が出るのか？整数だぞ？切り下げじゃないのか？
むしろforの条件式にn入れるのって自然ではないのでは？
この方式思いつかないと答えでないってこの世界ついていけそうもない、なんて考えていた。

コード③
お前n乗じゃなくて×nしてるやんけ！！！
ということで、自分で思いついた書き方でACできた。
頭に思い描いたコードを間違いなく書けるようになってきた思ってたのにどこか間違ってるんだろうなぁ・・・、とそこそこ落ち込んでいた。
そういう次元じゃない間違いだったから少しホッとした。
自分らしいミスといえば自分らしい。


余談
最初に思いついたn乗で割っていくのを正しく書き直すとTLEだった。
条件式一緒な時点でそこそこ遅いpowを同じループ数繰り返すのは無駄。
条件式にn乗したものを使えばいけそうな気がするんだけど、うまい入れ方が分からなかった。
そもそも早くなる可能性が存在しない可能性まであるからとりあえず置いておく。


もう1つ余談。
この問題をやったのと同じ日にダイクストラ法を調べていて、初めてcontinueなんていう関数を知った。
この問題の他人のコードを調べている時に、素因数分解を行う関数でcontinueを使っているのを見て結構な未来を感じた。
もともとループ内で無駄な宣言を省こうと考えて書いていたのだが、continueを入れるだけでずいぶんとすっきり見やすくさらに速度アップと来た。
繰り返し文では積極的に使っていきたい。

同時に、参照渡しした引数に結果を代入する形式からmap型の戻り値を持つ関数に変更した。
どちらが早いかは知らないが、複数の値を持ち得る戻り値にできることを忘れていた。
しばらくプログラムを書いていなかったため、頭に学生時代のCの「戻り値は1個だけ。複数戻したかったらポインタ型引数。」しか残っていなかった。
どう考えても戻り値設定した方が見やすいから忘れないように・・・。


次回はyukicoder No1のリベンジの予定。
ダイクストラ法の関数は作成済み。

ダイクストラ法は置いておいて、ひょんなことから目についたこの問題を解いてみた。
AOJは1度だけ挑戦したことがあるけど結局解けていなかった気がする。
テストケースが連続で入力されるせいで出力のタイミングが分からない、テストケースを確認しようとするもなぜか表示されない、簡単な問題だったからアルゴリズムは間違えていないはず、と何かがおかしいとやめた記憶がある。
今回ACを取るまでに、テストケースは入力ごとに出力すればいい、テストケースを連続で入力してまとめた場合は量が多いから表示されない、ということが分かった。
すなわちアルゴリズムを間違えていたのだろう・・・。





コード①
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3298606#1

まずは失敗作。
URLがどっか行っちゃったからACした後わざわざジャッジし直した。(失敗作のコードまでCtrl+Zで遡れるAtomすごい)
(1つの頂点を除いた三角形の面積>四角形の面積)になればその四角形は凹であると言えるはず。
最初はこの方針の回答を目指した。

三角形の面積は、ヘロンの公式を使って求め、割り算やら平方根を除いて誤差が出ないようにして大小関係の把握のみに努めた。
今回の一番の大仕事、三角形との面積の比較は頑張ってbit演算で実装した。
というのも、1年の時を経てまた競プロやってみようかなと思ったのが、このbit演算による部分が大きいからだ。

コード
https://yukicoder.me/submissions/304205


確か初めての競プロはyukicoderだったので、再開ということで初心に戻って雑に★2～★3あたりを解いていこうの巻。
やったことある感じがする、DPかな？という第一印象。
この場合のDPの書き方がすぐに出てこなかったから、誰かが愚直に書くのも勉強になるよと書いていたのを思い出しDFSで書いてみるもWA。
町nまでコストcで行くための関数をsolve(n,c)とすると、solve(n-i,c-[iからnまでのコスト])を1≦i<nで回して最小を取ればいいのではという方針。
今度は配列数を多めに取ってもだめだった。

解説曰くダイクストラ法で解くらしい。
高校の頃の記憶を掘り返してダイクストラ法を考えるのもしんどいし、一度勉強し直してから解き直そう。
今の知識量だと再帰でも解けるだろうとは思うけれど、ダイクストラ法でないと解けないのかもしれない。
やはり一度その辺りの知識をつけるのが良いか。



12/16 23:30 追記
コード
https://yukicoder.me/submissions/304478


問題文を見落としていた。
スタートの町とゴールの町が同じでも道は2種類以上あるかもしれない。
これに対応するためにVectorを3重にしたらTLE。
テストケースを見る限り答えは合ってそう。
もうちょっと良い対応の仕方があると思うんだけど思いつかない。
もはや経験不足しか感じない。
次はダイクストラ法を学ぶ。

コード
https://abc017.contest.atcoder.jp/submissions/3789176


競プロ初記事は初心者らしくACできない記事。
解説見ながらとりあえず愚直に書いてTLE。
しゃくとり法使って書くも、既に出てきた数字を探すのにfind使ったせいでどうも遅いが一応AC。
納得できずに高速化を図るもACが出ない。←今ココ
単純にdpの更新方法の認識が間違っている気がするけど、一度ACできた=アルゴリズムは間違っていないはず。
もう手が出ない。



12/15 6:00追記
AC取れた。
https://abc017.contest.atcoder.jp/submissions/3789283

サプリメントの総数N<サプリメントの種類Mがあり得るということか。
味の種類とはいえ普通総数の中で数えるだろう・・・。
確かにN≧Mとは書いていないけれど、これは単純に文脈から読み取れる内容ではないのか。
学校のテストならさすがに文句言いに行くレベル。

気づけたのはなんとなくVectorの要素数を最大限まで持っていった場合になぜかAC取れたから。
とりあえず配列系は要素数最大まで取るのが正義なのだろうか。
累積和使ってさらに高速化もしてみたいけどまた今度。