Educational Codeforces Round 104 反省とか - 文学徒が競プロをするブログ

1900位とか。もっと速く解けたよね？1000位くらいに入るべきだったなあとめちゃくちゃ反省。

A問題 Arena

最近のこどふぉでは一番良心がある問題。

int mini = *min_element(a.begin(), a.end());
int cnt = 0;
rep(i,n) if (mini == a[i]) cnt++;
cout << n-cnt << '\n';

これに1ペナ30分かかってるの大反省だな？
うーん。綺麗に図は書けて、

ということが分かったにもかかわらず、時間がかかりすぎてしまった。

$N$ が奇数の時は $(N+1)/2$ 進むごとに1スキップするんだと思ってしまったんだよなあ。式変形にしろ図を書くにしろ、考えやすい方策に落とし込めても、正確な情報を読み取れなければ意味がないんですよね。

図から数式に落とし込みたい時、僕の場合いきなり数式を書くのは混乱するので、どういう性質を持つのかを自然言語で表現しながら数式を考えると良いのかもしれない。今度やってみる。

これに2ペナ30分かかってるの反省してもし足りない。寝ぼけてたが言い訳にならないレベル。

Excelで表を書くと奇数の時は引き分けなしで良くて、偶数の時は良い感じに各チーム一回ずつ引き分けをいれるといいことがわかる。

雰囲気で実装したらWAが出た。よく見ると書いてた表とは違うものを出力していてたまげる。

今度こそ表と同じものを実装して提出すると、WA。首をかしげて表をよく見ると、引き分けの入れ方がカスで、全チームの勝ち点が全く等しくなっていないことがわかる。

ちゃんと表を作り直すとAC。これ30分くらい無駄にしてるの意味不明だし、B問題とあわせて50分無駄にしているのを考えると卒倒モノだなあ。

C考えるのが面倒だったのでDに行ったけど、これ速かったのえらかったな。

${a}^2 + {b}^2 = {c}^2$ かつ $c = {a}^2 - {b}$ となる $N$ 以下の $(a, b, c)$ を求めよというやつ。

因数分解とか出来るわけないから初手でwolfram alphaに投げると、 $a = 2n+1, b = 2({n}^2+n), c = b+1$ となることがわかるので、勝ちです。

特にbが $2({n}^2 + n)$ なので、 $\sqrt{n}$ より小さい物しか見なくていい。

よってそのまま実装すれば良いです。

数式ベースで考えようという最近徹底していた意識が活きたぜ。wolfram alpha最高！w
数式ベースで考えることを徹底しようにも、式変形が脳のメモリを圧迫して辛い気持ちになっていたんですが、とりあえずwolfram alphaに投げてもいいかもわからんね。

普通にわかんなかったな。通れない辺だけが定義されていて、ノードに重みがついているグラフが与えられるので、計算資源が無限にあれば補グラフにダイクストラ流して解けます。

単体の別記事で解法書きます。ググったけど日本語解説がなかった。