前からほんの少しやってすぐに飽きていたんですが、今回はKPCCというサークルでみんなでやろうという感じなので少し頑張ってみたいと思います。
解いた問題とかのメモをします。
AOJ-ICPC一日一AC、毎週AtCoder参加がノルマです。
アカウント：AOJ・AtCoder
8月3日
8月4日
8月5日
8月6日
8月7日
僕が解法に悩んでいた問題がだいたいDPということを神野さんに教えてもらった。
DPは知っているんですが、未だに使いこなせない。
適当に簡単な問題を解いてみた。
あと、下のDPの問題を解いてみようと思ったらTLEになったので、仕方なく他の方が解いた回答を見たらほぼ同じだったのでPythonのせいで通ってないみたいですね・・・。
ここまで慣れているPythonで書いていたのですが、そろそろ限界みたいです。
8月8日
やっと今日はC++で書きました。無限に時間がかかりました。
今日得た知見としては、小さすぎる値で「2.82327e-09」とか出力されるとWA扱いになるみたいですね。iostreamで出力する場合は下のような感じでやるみたいです。少し面倒ですね。もう少しいい方法があると良いのですが。
cout << fixed << setprecision(6) << dp[T][N] << endl;
【Proton.jp】 C++：マニピュレータを用いた数値の整形
KCPPのLT会で使ったスライドです。
8月9日
解法はすぐに思いつくような問題ですが、string型の数字を比較する方法など、C++の書き方で丸一日悩んでしまいました。結局string型の数字を比較するのは以下のように関数を作ることにしました。compareの挙動も分かりづらいです。
bool former_is_bigger(string a, string b){
if(a.size() > b.size() || (a.size() == b.size() && a.compare(b) >= 1)){
return true;
} else {
return false;
}
}
8月10日
簡単な問題ですが、C++でpair、sort、vectorを初めて使った。慣れない。
8月11日
DPで解くらしいが、制約が緩いので愚直に書いたら通ってしまった。勉強にならなかった。
8月12日
幅優先探索するだけなので1時間で解いてDijkstra法の勉強をするつもりだったが、無限にバグらせて時間がなくなった。
はじめてMLEが出た。
正直メモリをどれくらい使うのか意識していなかったが、地図ごとキューに入れるみたいな頭の悪いことをすると出てしまうみたい。
構造体やtypedefを初めて使った。
関数が配列を返せないのはとても不便。
D問題が解けなかった。
難しくはなかったが、僕の手が遅い。
あとは木の扱いに慣れてなさすぎるので、頑張りたい。
8月13日
簡単な問題を解いてDijkstra法をやるつもりだったが、やる気がなくなった。
8月14日
今日こそはDijkstra法をやる。
8月15日
Dijkstra法の問題が解けなかったので、とりあえず1問解いておいた。
最近、なかなか問題が解けない。
つらい。
今日もLT会がありました
8月16日
BitDP。やり方が分からず、かなり答えを見てしまった。
しかしだいぶビット演算の扱いが分かったので良かった。
O(n2)程度が限界。
普通のDP。
今日は実装が軽い問題を3個解いた。
練習としては良かった。
しかしDPは割とできるようになったので、最短路やグラフの問題を練習したい。
普通にユークリッド距離が1のときにマンハッタン距離が2になるということが数日分からなかった（頭が悪い）
8月17日
Segment木を初めて使った。
僕は無限に時間を使って書いたんだけれど、想定解は累積和というものを使うらしく、無限に頭が良かった。
AOJ 2600: Koto Distance - 宇宙ツイッタラーXの憂鬱
DP。
特定のテストケースだけWAが出るので原因が分からずにいたが、最初と最後の壁の処理で間違えていた。
愚直に解けばO(N)で間に合う。
調べたところ方針は現地点の左右の>と<の個数を数えるということで合っているみたいだが、
書き方が雑だったのでパネル数のカウントがややこしくなってしまった。
AOJ-ICPCの問題の横にある☆マークは良問であることを表しているらしく、この問題は星が7個もついているので解いてみたが、とても簡単だった。
幾何。簡単。
ICPCで解ける問題が減ってきたので、最短経路問題やフロー問題の典型題を解いていきたい。
8月18日
二分探索。
愚直にやるとO(230)でつらい。
いろいろ試そうと思ったけど、軽く枝刈りしたら通った（良くない）。
8月19日
幾何問題。
簡単だと思ったら、二つの円の交点を求めるところでつまずいた。
普通に調べてしまったけど、割と面倒だったのでこういうのをライブラリとして用意しておくんだろうか。
これくらいは導出しろという感じなんですかね。
分からない。
Dijkstra法。
簡単だけど、自分で書いたコードと人のブログに書いてあったコードがほぼ同じだったので嬉しい。
Warshall–Floyd法の練習。
Warshall–Floyd法そのままの問題。
最大フロー問題の練習として、二部マッチング問題を解いた。
ほぼ蟻本写経になってしまったし、最大フローを空で書けるようになるのは遠そう。
8月20日
とても簡単な問題だったがなぜか通らず、スタックを毎回クリアするのを忘れていた。
これに一時間くらい気付かず、辛い気持ちになった。
C++のstring型の扱いがわからず、B問題で時間を使ってしまった。
そのせいでD問題は方針はあっていたのに時間切れになった。
8月21日
二分探索。
問題自体は簡単だったが、C++の言語仕様が分からなくてpowをバグらせてしまった。
longの範囲でpowを扱いたいときには入力をlongにしないといけない。
考えてみればそうなのかもしれないが、このミスで時間を溶かした。
少し面白い最短路問題。
冷凍施設のない街を取り除き、時間がMより長くかかる道を取り除けば普通にDijkstra法になる。
しかも、計算量に余裕があるのでWarshall–Floyd法で良い。
取り除くところもO(N3)使えれば楽なので、そこも含めての優しさなのかな。
Dijkstra法。
Highway Express Bus | Aizu Online Judgeとほぼ同じ問題。
8月22日
考えることが色々とあるが、O(NL)で良いので丁寧に条件に合わせて書くだけ。
それでも無限にバグらせるので反省したい。
一応幾何問題でしょうか。
貪欲法でもあるしUnion-Find木問題でもある。
O(N3)で余裕があるので面倒臭がってUnion-Find木を使わずに解いたが、
結局そこの処理をバグらせてしまったので使った方がよかった。
8月23日
条件が色々とあるが、ただのDP。
それは良いのだが、dpの初期化で範囲を間違えて一つ外側まで指定していたのに手元ではエラーがでず、AOJでもエラーではなくWA扱いになってしまっていたのでハマってしまった。
頭が悪いので幅優先探索を4個書いた。
まだC++は分からないことが多い。
配列渡しを初めて使った。
配列の参照渡し - Passing days
8月24日
Dijkstra法。
これは面白い問題だったと思う。
高々24枚だからメモ化して全探索した。
こういうと聞こえは良いが、最初は普通に探索しきれるだろうと適当にやったら同じ状態をなんども踏んでTLEにすらならずREを出された。
結局状態をbitでメモしたので、bitDPの方が明らかに良かった。
8月25日
頑張って書いたら通った。
おそらく調べてみた感じでも頑張って書くしかない。
8月26日
幾何問題。
幾何ライブラリが活躍する問題だったので、幾何ライブラリを作った。
写経しただけだけれども。
幾何ライブラリがあれば、あとはひたすら距離を測るだけ。
問題としては面白くはない。
平面幾何におけるベクトル演算 » 直線と線分
ルールに則ってひたすら頑張る。
空間・時間ともに計算量に余裕がありそうなので、多めに候補をとって最後に暗号化して一致するか判定した。
復号化よりも暗号化の方が楽なので、結果的には良い方針だったかもしれない。
無念の1完。あとで解説をみたらBとCは方針が惜しかったので、次回は3完を目指したい。
8月27日
もはや競プロの問題ではない。解いていた問題が解けなかったので消化。
しばらくABCを埋めていきたいと思う。一応時間を計って行う。A、B、C問題はすぐに終わったが、D問題で悩んで結局1時間ほど使ってしまった。
D問題、アプローチは正しかったがパスを求めるのにDijkstra法を使ったらTLEになってしまった。実装があっていれば通る気がするのでどこかで無駄な事をしているかもしれない。木であれば単純に探索をすれば良いということに気づかずにDijkstra法などを使うというミスを何回かしているので気をつけたい。
C問題でTLEを出した。文字列結合は時間がかかるということを学んだ。
肝心のD問題をまた通すことができなかった。方針はわかったが、二項係数の余りの出し方がわからなかった。意外とD問題を通すことができない。つらい。
8月28日
今日もABCをやりたかったので消化問題。
久々に時間内にABC全完できた。1時間29分くらい。たかがABCでも嬉しい。
しかしB問題でなぜか1回で行ける場合を飛ばしてWAを出して時間を食ってしまった。こういうケアレスミスが多いのをなんとかしたい。
簡単な回だった。
C問題で例をちゃんと見ていなかったので色が8種類しかないと勘違いしてWAを出して結局45分かかってしまった。
8月29日
完全に頭が悪いので二分探索という発想に至らずD問題が解けなかった。
8月30日
探索するだけ。
8月31日
最初の面を決定する効率の良い方法があるのか少し考えたが、結局全て列挙した。他の人もそのようにやっている人がいたので良い方法はないのかもしれない。
D問題、最小値をlogNで求めたいから・・・segment木か。という頭の悪い発想のせいで時間内に実装できなかった。普通にヒープで良いじゃん・・・。
9月1日
ベルマンフォード法を使うだけの問題だが、ベルマンフォード法は意外と使わないので初めて書いた。そのため、負閉路判定でバグらせて悲しい気持ちになった。
A、Bを1時間ほど掛けて解いたが、Cが解けなかった。
9月2日
またD問題が解けなかった。想定解ではないものの方針は正しいと思うが、REとWAが二個ずつでてしまった。想定解は頭が良いですね。
またD問題が解けなかった・・・。必勝法を見つける問題はとても苦手。
参加。69位。ABC久々に全完できたので嬉しいけど、簡単な問題だった。D問題でtypoに気づかずにWAを出してしまったのが悔やまれる。
9月3日
いい加減、AB問題を解くのが面倒なのでARCを解くことにしたが、D問題すら解けなくて辛い気持ちになった。
D問題は部分点解しか得られなかった。方針としては惜しかったが、コードに落としこめなかった。計算量を減らす方法が複数あり、問題としては面白かった。
9月4日
C、D問題は解けた。簡単な回だったが、Dの実装が悪くてかなり時間をかけてしまった。
9月5日
C、Dは簡単だが、E問題は解けなかった。解説を見ても自分で解ける気があまりしなかった。E問題を解けるようになるにはもう少しかかりそう。
簡単な回だったようで、E問題もDPだろうとは思ったが解けなかった。DPはだいたい解けると思っていたので悲しくなったのでtypical DPコンテストでもとこうと思う。
9月6日
9月9日
Cしか解けなかった。Dは解説によると途中からは典型らしい。
一応全完できたが、単純ミスで2WA2REを出してしまった。問題としては簡単な回だったので反省したい。特にD問題は制約が8だからbit DPだろうという短絡的な発想をしてしまったが普通に全探索できた。bit DPをバグらせて2REを出しているので、簡単な方針を立てられるように心がけたい。
あとやっと緑コーダーになった。とりあえず早くシアンになりたいですね。
9月10日
E問題が解けそうで解けなかった。先に集合を作ろうという発想はあったが、座標の45度回転をしていなかったので順序集合で重複なく集合を作る方法が思いつかなかった。そのあとの二分探索もおそらく思いつかないだろう。実装としても僕からすると大変そう。やはりE問題はもう少し鍛錬が必要みたい。
9月11日
D問題が解けなかった。ゲームの勝敗問題は苦手。しかしE問題が簡単だったので解けた。簡単だったのでなんとも言えないが、E問題は初めて解けたので嬉しい。
9月12日
E問題も簡単だが、実装が悪くて間に合わなかった。
9月13日
久しぶりにAOJ。この問題はなかなか難しい。
9月14日
前は難しいかと思っていたが簡単だった。しかしbit演算をバグらせて時間がかかってしまった。
桁DP。
9月16日
E問題は方針が思いついたのが終了10分前くらいだったので解けなかった。 C、D、Eともに考察に時間を掛けすぎなのでなんとかしたい。
レート1117になった。次回シアンにいけるといいです。
9月18日
Raven38さんとcaretくんと出ました。僕はCを解きました。
9月19日
チームとしてはたくさん解けていたので楽しかったが、思い返すと僕はEしか解いていない・・・。
9月20日
Bを書いたら何故か無限にWAを出されて、2時間くらい悩んだ末にcaretくんからの提案でpython3で書いたら通った。c++とは分かり合えない。
9月23日
Dが解けなかった。想定解、頭良いですね・・・。マンハッタン距離問題は多いのでこういう考え方に慣れたいです。
あと水色コーダーになりました。わーい。
随時書き足します
