神野さんに言われました。

神野さんに言われました。

AIの勉強をしています @sesenosannko

競技プログラミングを始めた

前からほんの少しやってすぐに飽きていたんですが、今回はKPCCというサークルでみんなでやろうという感じなので少し頑張ってみたいと思います。 解いた問題とかのメモをします。

AOJ-ICPC一日一AC、毎週AtCoder参加がノルマです。

アカウント:AOJAtCoder

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日

とても簡単な問題だったがなぜか通らず、スタックを毎回クリアするのを忘れていた。 これに一時間くらい気付かず、辛い気持ちになった。

随時書き足します