2014-07-12
ICPC エア国内予選
Other | | 
国内予選当日に、お仕事しつつサブで4問くらい解いてみた。
A
税抜き価格の組を列挙して、税率変更前の価格に合致しているかでフィルタして、税率変更後の価格の最大値を取る。
競プロとしては基本的なことをやるだけなんだけど、プログラミング初心者のゼロ完防止といえるかはちょっとよくわからない。
自然な発想としては、変更前の価格から税抜き価格を生成して、変更後価格を求めたいと思うのだけど、対応する税抜き価格というのは存在性も一意性もないところが落とし穴で、たいがい実装とデバッグが悲惨なことになり、うまく実装するにはそれなりの経験が必要になる。税抜き価格を中心にして発想を逆転させて簡潔にするのが重要になると思われるけれど、それはそんなに自明だろうか？
むむむ。
B
どう転んでも問題文に書いてある通りにやるしかなさそう。
本当にやるだけ。
C
真面目にやるなら座標圧縮で離散的にやるとかしないといけないんだけど、冷静になって制約よく見ると座標は 20 までの整数値しか与えられないので、幅1の長方形に切ってそれぞれについて最大値を求めて最小値を取ればいい。こうすると原点をまたぐやつとか場合分けが減って嬉しい。
見た途端に2分探索という人もいたらしい。
2分探索の基本的な考え方は、特定のパラメータ (ここでは時刻) を固定した状況を考えて更新方向を求めるものである。
状況が複雑なのでこのような考察は重要となる。
なんだけど、よく考えるとこの問題については1次不等式にしかならないので、臨界値を陽に求めることができる上に、ほとんど計算式も同じになる。(そりゃ移項しただけだからな)
自分で実装するなら慣れてるものを使えばいいと思うけど、他の人に書かせるときにそれを勧めるならどうか思わなくもない。
D
ルールをよく見ると1文字につき高々2通りしかできることがないので、制約に注目すると 2^20 で押さえられて普通に1個ずつ作って (順序付き) セットに突っ込んでも良い。
よく見ると最大ケースはサンプルに入っている...。
実際の列挙は、先頭から DFS とかで適当に作れば良い。
ビット列によるエンコーディングでループを回すのはどうなのだろう？ビット列へのエンコーディングは計算量の見積もりができればほぼ自明だけど、デコーディングは局所的にはできなくて、結局 DFS のときと同様に先頭からやれば良いという考えが必要で、探索における分岐だと思ったほうが自然なのでは？と思った。
SRM とかで数え上げ系とか、辞書順最小とか求める問題では、たいてい1個ずつ馬鹿正直作ると計算量で大変なことになるので、その手のコンテストを中心にしていると生理的にちょっと辛かったかもしれない。
まあ、でも C より頭使わなくて良くて簡単では？
感想
- A はちょっとひねりすぎで、初心者には辛かったかもしれない。 (ゼロ完防止なら模擬と同じくらいの難易度にしても...)
- 問題にかかる時間が、実装よりも考察が支配的な傾向が強いせいか、国内予選は時間が短いこともあって、ボラティリティが必要以上に高くなってしまっている気がした。
- ゲームバランス調整むずい。やるの自分じゃないけど
2014-04-26
GCJ Round 1A
Other | | 
ダメすぎてオワってた。
A: 昔使ってた next_permutation ライブラリ引っ張ってきたら、仕様を忘れてて、最初1回分が飛んでしまって WA ではまった。どちらにしろ半分全列挙だーとかって書きだしたので、いろいろアレだった。
C: http://upload.wikimedia.org/wikipedia/commons/9/90/Probabilities7.svg を眺めてただけだった。Bias がない状態がパッと思いつかなかったわけだけど、一様になってるはず。そういえばちょっと前に Twitter でこの辺の話が話題になってた気がする。
あまりに杜撰なプレイだった。反省する。
2014-04-13
TCO 2014 Qual 1A
SRM | | 
1週間延期されたのがあった。
去年の TCO 予選シーズン以来 TopCoder に出ていなかったのでかなり久々。
Easy: 文字列に対して適当な prefix を切り出して suffix N 文字をソートという処理を繰り返して辞書順最小の文字列を作る問題。Prefix の選び方は1文字ずつ前進で N 文字になるまで限界まで続ける戦略が最適であるのが、考察するとわからなくもないのでそれを実装するとよい。もう少し効率よくするなら、先頭 1 文字を除いてソート、先頭 N 文字を切り出してソートが最終結果なのでそれを実装すればよい。全体ソートして先頭 N 文字を切り出すという嘘解法にたどり着きやすいけど "TOPCODER" で落ちるので、サンプル親切だった。
Mid: 文字を並び替えて辞書順最小の文字列を作る問題。ただし、元の位置から N 文字以上離れてはいけない。これは先頭から使える文字を貪欲に置いていけば OK。ただし、その場所を逃すと制約を満たさなくなるという文字が生じたらそれを置かないといけないことに注意する。
Hard: よくわからなかったけど 8N くらいの DP でいいらしい。
Challenge: 灰色さんが "TOPCODER" で落ちるはずの嘘解法を提出していたので3人くらい落とした。(実のところ1人目はTLE狙いだった。枝刈り落とそうとしてしまうのやはり辞めた方がいい。まあ結果オーライ)サンプルくらいチェックしようね？
3 年前の TCO の時期のレートを超えて highest 更新。あと部屋 1 位で div で獲得した最高のスコアだったらしいけど、div 1.5 みたいな感じなので微妙い。
GCJ 2014 Qual
Other | | 
Template を Java 8 にバージョンアップして出てみた。というより template 更新ばかりに時間をかけて危うく時間切れになるところだった。。とはいえ並列ストリーム以外は全然使ってないけど。
A: やるだけ。もうちょっと詳しく説明すると、 4 行 4 列の行列が 2 つあるのでそれぞれから指定された行を抜き出して一致する数字はいくつありますか？1つならその数字も教えてねという問題。まあ、登場人物は盤面を90度回転させればよかっただけのになぜそうしなかったのか、謎である。
B: クッキクリッカーで所定の枚数を最速で集めるには？ただし、施設は農場だけで(ばーさんもいない)、さらに連続時間モデル。建てる施設数をパラメータに最適化すれば良くて多分凸性もありそう。なんか制約から線形探索で良さそうな気がしたのでそれ投げてしまったけど通った。でも、あとでよく考えてみると C=1, F=1, X=100,000 とか渡されるとヤバイことに気付いた。これだからランダム入力は…
C: 盤面のサイズと地雷の数が与えられるので、1 クリックで終了できるような盤面を生成する問題。Small は全配置を生成してそれぞれ 1 クリックで終了できる位置がないか調べた。Large はそれでは無理なので、左と上に幅 3 の領域を残して角にクリックポイントを置き、残りの部分に規則的に埋め、次に幅 3 の領域に規則的に並べて、最後に残った 3x3 は全探索した。3x3 の領域に離接する外側のタイルでアドホックな場合分けを入れたので、そこで撃墜できそうな予感だったけど、落ちなかった。ランダム入力さまさま…
D: 問題文に警告が出ているように理解するまで時間のかかる問題。詐欺プレイをするときは釣りができるので、Ken の各おもりりに最大までそれに勝てる自分のおもりを割り当てることができる。一方、しないときは自分の持っているおもりの重さしか伝えられないので、避けられないとき以外は Ken によってそれより小さい重さのおもりが 1 個ずつ消費されてしまうので、残りが答えとなる。
結局全部通って満点 90 点でした。
2014-02-19
2013-06-16
ARC 14
Other | | 
夕飯食いながら参加してみた.
- A: パリティ見るだけ
- B: 1個ずつ確かめつつ出力はターン数のパリティ見るだけ
- C: 貪欲に各色のパリティを加算すればいい
- D: x + y の小さいクエリからイベント処理の要領で
フォーム直書き縛りとかもやってみた. C で文字列が入力に与えられているとは思わなくて 1 WA, 14 位.
C
筒の中に2個までは, 何が来ても貪欲にペアを消すことが自明に可能なので略.
3個目に消せないものが来たときを考える. 4個目の色を見て, それが消せるように3個目を入れる側を調整すればよい. この操作のあとは, 必ず2個になる.
このようにすると, 貪欲にすべてのペアが消せることが示せるので, 残る個数はパリティだけで決まる.
D
説明は略してソースコード
2013-06-03
GCJ2013 R2
Other | | 
初めてTシャツはもらえたっぽい気がするけど、ここで今年の冒険は終わってしまった。。
来年こそは最強のオレオレ言語でオンサイトに行くんだ...
テンプレ (改)
前のは実行方法が煩わしかったので、カレントディレクトリを読んで適切そうなものを実行するようにした。
しかし、これ WA ったときにファイル退避しないといけなくて面倒だし失敗かも。。とサブミットデバッグして思った。
2013-04-14
GCJ2013 Qual
Other | | 
最近は完全に引退勢でした。
A
Tic-Tac-Toe が 4x4 になって、Tomek (内輪ネタ...) なる X / O どちらとしても使えるものが最初から盤面に置かれている。盤面を見て勝敗を判定せよ。
やるだけ。
どちらも勝利条件を満たしているときの処理は invalid な盤面はないとのことなので無視して良さげ。
B
縦横1直線に同じ高さに刈れる芝刈り機があるので、与えられた芝の高さが作れるか判定せよ。
やるだけ。
縦横どちらかの方向でそのマスより高い芝がなければ良いので、各行・列の最高を求めておけば簡単。
C Small / Large1
閉区間が与えられるので、x, x^2 が回文となるような x^2 の個数を求めよ。
やるだけ。
x だけ全列挙しておけばよいので高々 10^7 個、あらかじめ求めておいてもよいのでさらに簡単。
C Large2
注: これはまともな解法ではありません。想定解法は他の人の解説を見てください。
実際に数えてみると 39 個しかないので、観察してみた。
すると x には次の規則性があるように見えた。(未証明)
- 1桁のとき
- 1, 2, 3
- 両端
- 1, 2
- 奇数桁のときの真ん中
- 0, 1, 2
- それ以外
- 0, 1
となり、列挙すべき候補がだいぶ減ったように見える。
実際調べてみると 40,000 ちょっとだった。
あとは埋め込みして2分探索。したけれども、ソースコードが大きくなりすぎて弾かれた。そういえばそういうのもあった。覚えていたら形式をもう少し考慮したのに。反則とられるのも嫌だったのでスルー。
Practice は通った。
D Small
箱の鍵がいくつか入った箱が幾つかあるので、全部開けられるような順番を求めよ。複数あるときは辞書順最小で。
Small は小さいので巡回セールスマンで解いた。直前の状態が何だったかを覚えておく必要はないので少し状態は減る。
D Large
マッチングに見えた。よく知らない。
結果
135 で 1205位。
おまけ
毎年 http://www.go-hero.net/ から去年のものを発掘してきてテンプレを作るのも賢くないので自分用にペタリ
2012-03-18
SRM537
SRM | | 
賞金付きなのでたまには真面目に参加してみる。
275
AとBがXと適当なYから作れるか調べればよい。AもBもXだけで作れてしまうならYは何でもいいので-1。それ以外のときは1<=Y<=max(A,B)の範囲に収まるので全部調べて数え上げる。小さいのでユークリッドの互除法とかは不要。
200.27
http://community.topcoder.com/stat?c=problem_solution&rm=312058&rd=14730&pm=11817&cr=22695644 (要ログイン)]
500
Bit別に処理できるので、各部屋の各bitが1になる確率をDPで計算していけばよい。
352.97
http://community.topcoder.com/stat?c=problem_solution&rd=14730&rm=312058&cr=22695644&pm=11822 (要ログイン)]
925
Euler Cycle を貪欲に取り除いていくのではダメなんだろうなあ。と思いつつ放置。
Compiled.
Challenge Phase
TLE狙いで撃墜しようとしたけどミスした。あとで見たらWAだった。
-25.00
結果
528.24 で 103位。1374 -> 1534 で黄色復帰。闇雲な撃墜をやめたい。。
2011-06-24
ACM-ICPC 2011 (エア)国内予選
Other | | 
すでに引退しているので裏方でした。低速で何問か本番やっている裏で解いてみました。大体30位相当かな。
A. チェビシェフの定理
適当。途中で2倍しないといけないことを思い出した形跡が。
B. 世界の天秤
適当。Stackに積んだように見える。
C. 同色パネル結合
最後の色が指定されているのを忘れて時間かかった。図が多いと縦に長くなるので、横長ディスプレイだと忘れずに読むなんて無理な気がする。マジックナンバー多くてちょっとひどいコード。
D. そして，いくつになった？
適当にメモりつつ探索。最初leftがimmutableな使い方していないことを忘れてmapに突っ込んでしまった。反省します。
まとめ
みなさんずいぶんハイレベルになりましたね。しみじみ。いつも1歩大学内トップチームにいくらか及ばなくて、あまり解けていないのに地区予選に進出するチームを苦々しく思っていたものですが(後継のチームはずいぶん強くなりましたが)、全体のレベルが上がると気持ちがいいものですね。
あと、ペアプロ懐かしいです。僕と契約して以下略。
おまけ
練習セッション大事です。使い方覚えて無意味なWAを出さないというのもそうですが、様々な不具合によりログインすらできないということがしょっちゅうあるので、きちんと動作確認に協力してください。お願いします。
と、模擬国内予選運営して思いました。
2011-05-21
Google Code Jam 2011 Round 1A
Other | | 
1問しか時間内に通らなくてほげほげ。
A. FreeCell Statistics
できないのは、PGが100または0なのにPDがそうでないとき、Dの最小値がNより大きいときだけです。Dの最小値は約分すれば求まります。
28m 23s
B. The Killer Word
適当にソートして範囲を狭めつつ調べるつもりでした。90分くらい間違った方針で書いていたので時間内に終わりませんでした。で、終了後25分くらいで書けたコードはLargeが10秒くらい。
1 wrong try
C. Pseudominion
読みませんでした。
まとめ
最近スタッフ側にまわってタイムリミットなしで解く方が多くなったせいか、実装が遅すぎですね。トレーニングします。