Codeforces Round #297 (Div. 2)

概要

つらい回だった。

経過

Div2 onlyなのでPascal回にしようと決意。

A問題。やるだけ。Pascalが思い出せなくて時間がかかる。

B問題。ちょっと考えると反転の軸は文字列の中心であることがわかるので、反転の左端と右端をメモして、実際に反転させながら出力していく。

C問題。Bより簡単。長方形の面積は、周囲の長さが同じなら縦の長さと横の長さが近いほど大きくなるので、できるだけ長さの近い棒同士で作るのが正解。後は、長い棒を優先したほうが面積が大きくなるのは自明。

がしかし、この問題、答えが32bitに収まらないので64bitを使う必要があるが、なぜかサーバーではint64を使ってもオーバーフローする(後述するがよく考えるとそんなことなかった)。ので、乗算と加算をサポートする多倍長整数を実装した。AC。

試行錯誤の跡。

gyazo.com

本当に64bit整数が使えなかったのか

Pascalのintegerは16bit。これでA問題はとても悩んだ。32bitを使うならlongintを、64bitを使うならint64を使う必要がある。

ローカルではint64を使用すれば答えが正常に出力されたが、サーバーだとオーバーフローしていた。D言語のバージョンがDMD32 v2であることから、FPCも32bit版であることが原因でint64が使えないのではないか(=longintと同じになっているのではないか)と推測した。

しかし、FPCのソースコードを検索してみると思いの外使われており、それらは普通にint64で通っていた。そして、改めてコードを見なおしてみると、次のような箇所が発見できた。

ans := ans + b * c

ansはint64、それ以外はlongintであり、bとcは棒の長さである。

当然のことながら、b * c の型はlongintだろう。

オーバーフローして当然だ。ローカルだとコンパイラが気を利かしてくれたのかも知れない。

まとめ

Pascal力高めたい