ICPC韓国サイト
大会本番中なに考えてたかとかを書きつづってみる
事務的にどういう感じだったかは
miracjpさんの日記を参照のこと
開始前
会場間違えたりいろいろあってどたばたしたけど
なんとか会場入りして待合席に着く
アナウンスが韓国語で、入場しろという指示が聞こえなかった
周りのチームに英語で聞いたら、入場しろという指示だと言ってくれた
その後の彼らの会話は韓国語で分からなかったが、雰囲気
「英語の会話だぜ、パネェ」って感じだったと思う
開始0分
問題を開く、問題が1部しか入ってないのでAを他のチームメイトに
渡して、Bから読み始める、どうもやるだけ…だよなぁ
Cを読む、これもやるだけっぽい…、どちらも実装次第って感じだ
チームメイトに任せたほうがいい
開始10分
Aが通って、Bを渡す
開始40時間
Bが通って、Cを渡す
開始1時間
DとEを読む、Eはすぐにわかる、Dは、すぐに思いつかんが、miracさんに渡せば
どうせ30秒くらいで答えが返ってくるだろうと思って話したらやっぱり30秒で
答えが返ってくる。
開始2時間ちょろ
この時点でD（Dは1WA）もEも通る
さて、後半の問題を読むがまったくわからん
難易度が前半と後半で極端に違う気がする
少し周りを眺めると、真正面のチームがやたらと問題を解いている
それ以外は、五十歩百歩がうち含め4-5チーム、うわぁ…やな展開ですぅ
早解き5問のちょい難易度高めが5問
2位は時間勝負が1問飛びぬけた奴が勝つことはこの辺で覚悟する
時間で負けているから、問題数で勝つしかない
開始3時間ちょろ
FとIについて、それなりの解答が出来上がる
Fをmiracさんと実装開始、Iはnkamaeさんが机上実装
Fをなんとか通した時点で3時間40分くらい
Iに交代、Iを完全にnkamaeさんに任せて
個人的に気になっていたHに取り掛かる
開始4時間ちょろ
どうもデバッグに苦戦しているらしい
miracさんがI問題に合流、僕はまだHを考える
開始4時間半
まだデバッグが終わらない、僕もIに合流する
終了2分前
ようやくサンプルが通る
投げる…頼む、通って下さい………………
AC、この時はさすがにガッツポーズしてしまった
ここで5時間
総評
結果、公式4位、非公式6位
KAISTの最強チームが本当に強かった
_の最速パラレルくらいの速度で次々と問題を解いていた
うーん、やっぱり、なんというか、なるようになった結果という感じだった
できなかったわけではなかったし、かといって実力以上かといえばそうではない、みたいな
まぁ、偶然でもスロット取れたらよし
取れなくても練習になったからよしということで…
なんか書いてて思ったけど、ほんと情報量ないなこの日記
japljコンテスト参加記
お久しぶり過ぎて・・・・・
お久しぶりです。今回はjapljコンテスト参加記。
Aを開く、読む、うーん、なんか関数を再帰的に定義しているらしい。
F1を書いてみる、ほうほう
F2を書いてみる、ほほう、山々ができてくるわけね
山の個数は2の累乗個、の前後、解けたーーー
投げる、「30パーセント正解」
なん・・・・・・だと・・・・・・
コーナーケースがあるんだろうなーとか思ったが
問題が単純なため、気付くのに時間がかかると思い、Bを読む
なるほど、K番目になりうる物を出力か・・・・
個人には力の優劣がついていて、遷移する・・・
力の関係をグラフにするとDAGね
おー、トーナメントの結果はその一部を埋めてるわけね
で、K番目までになりうるのは、優勝者から距離Kまでにいる人
DAGだしDFSすりゃいいじゃん
入力がパースし辛い・・・・投げる、おお、通った
Aに戻る、コーナーケース無いかなー、おお、なんかループ回す最大値ちげーし
投げる、30パー正解・・・・うーん・・・・お、これPが0の時だめじゃね
投げる、通った。
Cを読む、なるほどね、線形でやれと、なんとなく、隣り合ったものはつなげたい気分になる
辞書順最小が線形でもとまるのだから、たぶんそうだよねーー、これGreedyにやりゃいいんじゃね
スタックで適当にGreedyっぽいコード書く、投げる、通った
ここらへんで1時間半くらい
さて、hosさんたちも相当苦戦しているらしい
これ俺なんかが解けるのか
D,E,Fを全部読む、知るかこんなもん
とりあえず100パーねらいのコードを目指して、残り45分切ったら部分点狙いに切り替えよう
Dを考える、0以上かどうか判定するのにどうしても時間がかかる、しかもなんだこのタイルの
繰り返しって・・・・・謎ゲーすぎる
E、そもそもある時間を見た時、大きさN以上のものを判定するのにも工夫がいる
これはあきらめる
F、見た中で一番まともそう、計算量的な観点で見ても明らかにDP・・・・なんだけど
どやってやるの？とりあえず一つサイクルを作ると、その内部には枝を張れないから
そのサイクルにつながってる先のツリーの部分グラフすなわち部分問題に分解できるのは
わかるけど・・・・・・まぁ、ただでさえDP苦手な俺が解けるのか・・・・
ここで45分来る、あちゃー、まぁ、部分点狙いで
Dの全探索コード書く、投げる、0パーセント、なん・・・・・だと・・・・・・
考える、考える、焦る、一回別に書いた奴投げる、0パー・・・やっべー
あ、wとh逆にしてる・・・・orz
まぁいいや、投げる、15パーを期待したら予想に反して30パーが返ってくる
次の15パーも結構イージーだったのね
ここで試合終了
JOIみたいな部分点方式は初めてでとても面白かった
また、こういう形式でコンテストをやってほしいと思った
正直最後、バグがなければ、EFの部分点コード書いて投げたのに・・・
実装力無さ過ぎ・・・・反省、こういうのがあるのがJOI形式の面白さなんだろうな
追加で書くと、Dに関して試合後ちょっと考えてた、これ大きさdの格子で区切れば、あとは
長方形のクエリのサブ問題に落ちるじゃないの・・・
長方形クエリなら2DBITが使える
だが・・・・クエリ数多すぎてこれでもだめか
クエリを平方分割するというアイデアが浮かんだけれど
それでもたらない、うーんバイナリーサーチできるの？
アイデアはあっててそれをうまく使えてないだけかなぁ
だけど、それくらいしか思いつかないよなぁと思っている
綺麗かつ新鮮な解答を期待ってことで・・・・
Google Code Jam R1A
えーっと
久々の日記になります
前回の日記の後、Div1に昇格したりICPCWFに進めたり
いろいろあったけど
GCJの参加記を書くことでまた日記をつけ始めたいと思います
解法解説などは本家様にもあるし
本番中何を考えながらコーディングしてたかを書いてみる
まず始まってAを読む
うーん、よくわからんが簡単なやるだけゲーらしい
書いてみる、セグフォ起こす
りんごさんが全完しててやべぇって思いながら
20分悩んで、cin>>n>>mとすべきところをcin>>n,mとしていた
事に愕然とする。
投げる、Small通る、うーん、まぁLargeも通るだろ
動かしてみる、3秒くらい答えがかえってこなくて焦るが
一応答えが出たので投げる
次、Bを読み始める、DPっぽい匂いを感じて簡単に定式化してみる
100*300*300*300なんてとても間に合いそうにない
なんやかんやごちゃごちゃやってみたけど
Smallすら複雑そうだったし結局50分くらい悩んで諦める
Cを読む、うーん、複雑
ちょっと自分でいくつか簡単な例をやってみる
うーん、二つの数字の大きさが切り替わるポイントまで引けるのか…
（これ以後A>Bとして話をしています）
？次の仕切り直しのゲームは要するに（B,A%B）…これってどっかで、おお！
ユークリッドの互除法だったのか…
それにしても必勝法がみつかんない
いろいろやってみる。そもそも絶対勝てる状態ってどんなの？
AがBの倍数の時、うーん棒グラフみたいなので書いてみる
？つまり仕切り直しになるまで引けるのか、kっていう数字の取り合い…
おお！NIMゲームを次々にやるのと同等ではないか！
これ先手必勝か！
書いてみてサンプルを動かす、合わない
？よく見ると先手は最初にk=1しか選べない
ふむ、先手と後手が入れ替わるのか
最初にk=1を選ばなくてはいけない数をカウントして
そんでもって先手を入れ替えて、k=1以外を初めて選べる人必勝か
けど明らかにそんなんLargeは間に合わない
まぁいいや、とりあえずSmall書いて投げよう
投げる、通る、そして残り30分
うーん、どうせ解けないしC-Large考えるか
そもそも2回以上1が出てくるときってどんなんだろう
うーん、あるAに対してαAがBだったとして、それの商が1だと
で、その次のゲームも1のときってなんとなくαB=A-Bだったら嬉しいよね…
式にしてみよう、α^2+α=1かぁ…解いて(-1+sqrt(5))/2
なんのこっちゃ、で時間切れ
アナライシスみてるとやっぱこの数字関係あったみたいですね
結局R1通過、けどこの出来はなぁ…Bくらいは解けるべきだった…
精進しよう
Texの余白設定について
久々の更新、サボらずやろうと思ったのになぁ、まぁいいや
今回はTexの余白設定の話
jarticleのA4標準設定では余白がでかすぎるから縮めたいと
けどネットを調べると設定が書いてあるだけで
なんでそうなってんのかが全然わからないので調べてまとめてみた
他のページとかを見てると余白の設定にはいろいろあるが
設定は大体このように行われるらしい
左右:左からベースラインの幅+ベースラインからの幅+本文の幅+etcというふうに幅が指定されている
普通はetcの部分を気にする必要はなさげ
横がどれだけ飛び出ようが構わない、左の余白分、勝手に右からも余白をとってはくれない
上下:ベースラインの幅+ベースラインからの幅（これの中にいろいろ細かい設定があるが今は気にしない）
- 本文の縦幅+etc（この中にページ数表示とかの設定が入ってる）というふうに幅が指定されている
下にどれだけ飛び出そうが構わない、下に行ったら勝手に改ページしてくれるわけではない
で、ここで
じゃあA4の幅ってinchに直すといくらなのかというと
横幅8.268inch×縦11.693inch（210mm×297mm）
通常の設定だとおそらく横はベースラインの幅1inch+ベースラインから0.5inchつまり左から
1.5inchのところから本文が表示され、本文幅が5.26inchとられている
つまり8.26-5.26-1.5=1.5となり、「右からも1.5inch」余白が取れているように見える
縦も同様に上下の余白が合うような設定になっている。
つまり、右余白も含めての合計が8.26inchになるようにすればいい
で、以下設定例（今回は横幅のみ）
\oddsidemargin 0.0in ←ベースラインからの左余白を消す
\textwidth 6.25in ←本文領域
これで8.26-6.25-1.0=1.0で左右1inchづつ余白が取られる
上下はもうちょい話がややこしくて、ヘッダーフッターなどの設定が混じるが
基本は一緒
設定のしかた、どこがどう設定出来るかについては
ググると画像付きの丁寧な解説が見つかるはず
ところで、この余白設定、inchだけではなくmmでも指定できる
ほんとにびっちりあわせておきたい人はmmで指定するといい
付録
デフォルト設定では多分\headheight+\headsepで0.5inchとられている
\footskipのデフォルトは0.45inch
フッターなどの幅のデフォルトはおそらく0.1inch
設定に困っている誰かの役に立てば幸いです…
アマルフィ+データ保持の感覚の話
まず前半
アマルフィを見に行った、面白かった
織田さんかっこよかった、外交官役似合ってたし
天海さんの演技力がやっぱ異常だった、すごいの一言
是非見に行って見てください
さて、後半
大学からプログラミングを始めて、ICPCに出場して
いろんなの人（特にうちのチームメイトとか）の
コードとか、ライブコーディング（まぁペアプロしたらそら見るんだけど）
とかを見ていてずっと違和感があったことが最近解決した
普通に人間が物を処理している単位と
コードをたくさん書いている人の物を処理している単位の
歴然とした違い、それを最もあらわしてそうな例
ICPC的に、以下のようなデータが与えられるとする
10:15:23
11:23:56
23:55:55
……
見ての通り、24時間表記の時計
これを保持する変数、どやって宣言する?っていう話なんですが
チームで問題を解いてる時
俺が
int tokei[100][3];//もちろん100は時刻の数、3は時、分、秒
//tokeiなんて付けんわな普通
とやろうとしたとき
コーダーは、ノータイムで
int tokei[3][100];
とやったわけです
実質的には一緒だし、だからどうしたって話なんですが
これってすごいことだと思いませんか
だって、パソコン的には処理の仕方の「区分」は絶対に時、分、秒で分かれてる
けど俺はそれを「時計」単位に区切ろうとした
歴然とした差が出てる
その顕著な例だと思った
なんか妙に感動というか、感心というかしてしまったので書いてみた
つまらんかもしれんけど……大事なことだと思った
Topcoder SRM445 Div2
あの1000が通せないとことか
まさに自分っぽかったSRM
ちょっと規則性がぐちゃぐちゃになると
考えるの放棄してる
思考の整理をちゃんとしなきゃ、気抜けすぎ
精進しよう、この欠点を超えれば、ブルーの上位には、いけるはず
さて、内容ですが
300
文字列が与えられて、それを、ある文字に置換することを考える
文字の変換規則は全単射であればいい
様々な変換規則の中で変換後の文字列が辞書順最小になる規則を見つけ
変換後の文字列を答えよという問題
前の文字からa,b,c,d…と変換してやればいい
以前現れた文字はきちんと同じ文字にすること
500
二次元平面グリッド上に50個までの点が与えられて(座標は整数)
グリッド格子点のうち、上下左右にそれぞれ点があるような座標はいくつありますか？
という問題、座標が-100から100までと非常に小さいので
全座標で調べりゃいい
1000
10桁までの2進数を以下のように並べ替える
1、一つ前の数とは、1をいくつかか、あるいは0をいくつか反転させたもの
2、そのような列で、2^nまでを全て並べられる
3、なおかつ、出来るだけ辞書順最小（ある整数は表れられる最小の位置に出てくる）
でk番目のものを探す
規則性があって、下二桁とそれ以外に分けて考える
…けど規則性を整理しきれず解けなかった
感想、マジ300と500が反射早とき実装ゲーだった
1000が通せなかったのが悔しいというか
何が悪いか分かってる分余計になんかびみょーな気分
精進あるのみだ
追記
なんか規則性の糞もなかったようだ
うう…問題を難しく考えすぎてしまうようだ
