2004/Teams/combat result - ICPC OB/OG の会

メンバー †

田中
金城
村主

第四回模擬練習会(なんとなくコメントつき) †

色々と不手際があったので一時間強ほど経ってからの参加となりました。急な参加申し込みでその節はどうもご迷惑をおかけしました。オンラインでの参加でしたが、頑張ってリモートアシスタンスを使って XPをやっておりました。

・解いた問題たち

一目で簡単そうだったので真っ先に解きました。桁数についてシンメトリーなので、絶対値が9ぐらいまでの GSC表記を作ってみれば法則が分かるだろうと思ったら思ったとおり分かりました。負の数の剰余とかは触らぬ神にたたりなし、なので全部正の数で処理しています。そのせいか、なんと3パスです。

10進数→(絶対値を)普通の3進数→GSCに変換→(負の数だった場合)負の数のGSCに変換

どうも、普通に一発でGSCに変換できるみたいですが、これでも10分ぐらいで終わったのでOKです。あと、入力に-2^32があったので、一発目オーバーフローでちゃっかりWrong Answerをもらいました。結局 long long int のお世話になっています。

b4.cpp

一目でめんどくさそうだったので、飛ばしました。私(田中)が他の問題を解いているうちに村主君が解いてくれました。多分、めんどくさいだけの問題だとは思う。

g4.cpp

一目でDPだと思ったので、これは解けないとまずいような気がして必死で解きました。最初思いついた(とまでは行かないか…)のが1024!なアルゴリズム。それをちょっとひねって2^1024までは自明に浮かびました。その後5分ぐらいうんうん考えていると、どの数字を使ったかどうかを覚えておく必要が無いことに気付いて (メモリ使用量が)O(n^3)な解法を思いつきました。それだと1024に対してはメモリがたらなさそうなのでもうちょっと考えてO(n^2)な解法を作成。実装自体は簡単でした。解法は模範解答と多分大体同じですが、私の解法では、直前の数が何番目に大きいか?では無くて直前の数より大きな数が何個残っているか?を考えています。 …同じですね。失礼しました。

・解けなかった問題たち

d4.cpp

実はこれ二番目に解きました。何べん送ってもアクセプトしなくて非常に悲しかったです。解法は普通にsetを使ってごりごり幅優先探索を実装。盤面は石一つを4ビットでコーディングして全体を40ビットに。 long long で保持。実は探索空間が爆発しない確信は全く無かったのですが、 10の倍数な場合は大体結構短手数で終了するような気がしたし、石は減る方向にしか変化しないのでいけるとふみました。実際のところ効率的な解法はないと思われます。アクセプトしなかった原因ですが、同じ場所の石と合成していたのが原因でした。こんな間違いもありました〜、という風に解説で聞いたときはそんなあほな間違いどこがやらかしてん？とか思っていたのですが、うちでした。しかし、確かに最初に石を消したんだけどなぁ、と見てみると、石を消す操作が純関数的だったので (ホラ、私ってHaskellerですから…？) どうもその辺でおかしなことになっていたようです。しかも、さらにその辺一回デバッグで手を入れて代入操作も追加していたので完全にそのあたりの操作は "紛れて"しまっていました。こうなってしまっては何ぼ見返しても間違いは発見できなかっただろうなぁ、と久々に背筋の寒くなる出来事でした。

c4.cpp

これは一目では簡単ですけど、実はちょびっとだけ煩雑ですね。私は今回英文は一切読んでいないので(完全に他人任せ出ございます) 問題の条件を正方形じゃなくて長方形と勘違いしていて、角度の区間を考えたらいけると力説する金城氏と村主氏に「いや、それではイカン。イカンですよ。」とか、よく分からん説得をしてしまっていました。それで、D問題の後回し、G問題の後回しにして、結局時間が無くなって手をつけず。全く駄目ですね。正方形と分かれば作るのは一瞬なので作りました。解の検証はしていませんが…。

i4.cpp

これも一目で簡単そう。実装も簡単そう。本来なら解かねばイカン問題ですけど、完全に時間オーバーですね。四辺が見えているという条件より点のmin,maxを取れば四隅が分かる。四隅が分かればそれに乗っかってる物が分かる、それをトポロジカルソートだ！。といったところで残り時間15分。静かに終局を待ちました…。さすがにこれを15分でデバッグまで完了できる自信は全く無いです。そういうわけで、これも終了後の作成に。妙にソースが汚いですが。

・その他の問題

すみません。未だに読んでいません。

↑