キーキの備忘録

記事としての体を成してるものはほぼありません。

RCOハーフマラソン2017

RCOハーフマラソンの参加記です。


予選

貪欲。

本戦

A問題

本番

sellコマンドの最初にnを出力するのを見てなくて20分ぐらい取られた。

  1. 30以上買ってくれる客に売れるなら売る(sell)
  2. タンクの容量が合計40以下なら一番小さいのから取り替える(change)
  3. まだ石油入れてないタンクに石油入れる(fill)
  4. 上記をすべてやっていて、単価30以下か、現在のタンクで支払えない客なら帰ってもらう(pass)

っていうのをifelseで書いたら、その時点で5位ぐらいだったのでそれ以降ほぼ手を付けなかった。

最後に売る客のしきい値を25に変えたら60000ぐらい上がったのでそれだけ。 現在のタンクの組み合わせで実現できる数が少ないとき(同じ容量のタンクばっかりとか)にやたらパスしてたので、その時もchangeするようにしたかったけど時間足りず。 最終 6315976点 13位

反省

解説で聞いた、売るときにどのタンクから売るかを考慮に入れてなかった。 sellでハマってたときにテスターのバグとすら思っていた(テスターのデバック上ではnにあたる数しか表示されず、手入力で入力を与えたら普通に出力されたため)ので、出力の形式はちゃんと読もう。(というか解答側が自由に個数指定して出力する問題で個数出力し忘れるの何回もやってる気がする……。)

B問題

本番

方針が定まらずとりあえず貪欲書いていろいろパラメータいじって試してた。 この時「ターン数かけてきっちり揃えに行くより数百ターンで雑に近づけた方がいい」と思ってしまって方針を間違えた。(移動不可な場所を壁として経路探索してたのでターン数かけると時間が足りなくなってたのも原因)

最終的に、 ゴールの位置が外側の車から動かして

  • ゴールへの経路があるものはその経路に従って進む。
  • 経路が無いものは
    • 2割の確率で壁を無視してゴールにまっすぐ向かう。
    • 8割の確率でランダムに動く。

というふうなのを300ターン行った。

最終 8918点 22位

反省

ランダムに動くときに動ける方向のみから選ぶだけで点数もっと上がった気がする。

→実際に実装してランダム移動する確率5割ぐらいにしたら2倍ぐらい点数上がった。

全体

最終順位:13+22=35 で全体13位 学生8位 社会人のおこぼれで賞金をもらえた。 プロコンで入賞できんたのが初めてなので嬉しい。 雑に点数が取れる方針を立てる能力は高いので、自分に有利なコンテストだった。(テスターなどがJavaで提供されてるのも有利)

RCO紹介

競プロer向けにわかりやすい企業紹介だった。 17時出社が魅力的だった。

懇親会・解説

B問題のビジュアライザを用いた解説は見ててとてもおもしろかった。 ピザとチキンだけだったので胃に重かった。 8時に新幹線だったので早退した。

反省

コミュ力。

終わりに

4時間ぶっ続けで考えるのは疲れるけど楽しい。問題も面白かったので、またあったら参加したい。

その他

・マウスを忘れたので近場でマウスを買った。

・朝7時起きは辛い。

・A問題のテスターはEclipseのMainファイルと同じ場所置いてテスターのmainメソッドに

command = “java -classpath bin Main”;

 と書くとEclipse上だけでテストできて便利だった。

・B問題は出力をテキストにするためにわざわざ自作ゲームライブラリのテキスト出力クラスを使った。(絶対コマンドライン使いたくないマン)

 ・Eclipseに出力をファイルに書き出す機能はありそう。

A問題

読んだけど飛ばす

部分点Cにあると思ってた。部分点狙う。

1つか2マス移動してゴールめざす。N=8ならMODいらないかな。

ごーるする順番の数だから最大は順列で8!かな?

ゴールが妨げられる場合は2つ異常連なっててさらに移動したらゴールしちゃうとき。 つまりゴールx=0から複数個連なるのが途中で出ちゃうとき。

xが(n-1)*2内にn個以上ロボがいるとき最初のゴールがnに制限される。 一回制限されるたびに次のnがひとつ下がっていく。コレで行く。

かんがえるちからがなくなった なにもかんがえられない

8 1 2 3 4 5 6 7 8

B問題

部分点狙いに行く

横を記憶して縦に書き出す問題。N=3の場合のみを考える。 はば優先探索でとりあえずやってみる。

部分点は取れた。charじゃなくてboolにして枝刈りしたらいけるかな。まああとで。

まとめ

脳が正常に働かなくなったので撤退。最近脳つかいすぎてたかな……。なにもかんがえられないだめだ。

AGC010

いつも通りにコンテスト中に考えてたことそのまま書いてる

A問題

偶奇の問題。足せばきは遇に遇は遇になるから木の数が偶数ならYES

AC

B問題

一周回りながら減らしていく問題。1~n足したやつで割り切れなければとりあえずNO

割り切れればその数が集会する回数。

½(n+1)n忘れてた。

集会する数をkとする。 とりあえずずらして足したやつ見る。 1234 2468 3575 1 1 1 -3 4646 2 2 -2 -2 5357 3 -1 -1 -1 12345 57468

うーんDPっぽい。でも普通にやったらメモリ持たなそう。とりあえずやる。

いやDPでも毎回N*Nあるから無理じゃね?

一番小さい数字を1~nの数字で分割する?

数字にNたしてkずつ上がってたらいいんじゃね?なんかコーナーケースありそう。 6 9 12 5 13 3 3 3 -7 -2 113 122 3 3 3 -2 -7 1 1 1 1 1 12345 34512 23451

なにもなければ次との差はk、切れ目があれば次との差は切れ目の数*nでこれを調べればいい。

WA 

オーバーフローかな……。区切りの数がkと同じか確かめるやつも入れてみた。

多分オーバーフローだった……。 AC

C問題

頂点から石を取り除く問題もう時間無いし無理そうとりあえず他の問題見る。

D問題

とりあえずこっちしてみる。数字から1引いて最大公約数で割る問題? なんか全部から1引いて足したの2で割るクソコード投げたけどまあWA。


終了。頭の隅にちらっと出てきたやつを考えずにまっすぐ進もうとするのをやめないと……。

ARC068

C問題

5と6を往復させてれば最初はいける。最後に1か2がくるとどうだろう?

どっちでもそれとは逆が最後に下にくるようにすればいいだけか。なら小さい数字が厳しそう 1~6は大丈夫。

x点ちょうどだと思ってた。以上なら簡単じゃん。

提出。誤読気をつけないと……。

AC。

D問題

抜き出すカードは1枚は重なってるカードじゃないと意味ない。 残るカードはそういうカードが存在するかだけが重要。

同じカードの奇偶で調整。とりあえず1枚か2枚になるまですべての種類で減らす。 いやこれだと3344455のときが……おかしくならないな2枚あるの保証されてるからそれ選べばいい。

カードの種類+(偶数の種類の和が奇数のとき-1)?

例で試す

4-1

7+0

例はそうっぽいとりあえずこれでいく

提出した。ちょっと怪しい。

WA。2残ったやつの消し方もっと詰める。 でもこれもうつめられなくね

案の定コードミスってた。最後の種類の数の偶数カウント漏れ。

AC。

E問題。

特定区間でのみ買える品をすべての間隔について何種類買えるか。 つまりいくつの区間に接触出来るかをすべての間隔で調べろってことかな?

脳が死んできた。

間隔がd以上ならdにはそれが必ず含まれる。 なんか数直線をいい感じにして入ったら+出たらーして数えていく方法使えばできそう。名前忘れた。

戻ってきた。時間無いけど。

F問題

EわかんあいからFちょっと覗いた。

1は始めにいれるからあとはK-1回とN-K回それぞれ入れられてその組み合わせを割る?

つまりN-1からN-Kを選ぶ組み合わせっぽい?

誤読してた……。食べるのもどちらかから指定できるのか……。

もう一回組み合わせ計算していい感じに掛ければいけそうと思ったけどそもそも前提破綻してるじゃん。

無理そう。

終わり

なんか最後の方無駄に頑張らずに復習のために体力残しておくほうがいい気がしてきた。 誤読は多分どうしようもない。

AGC008に参加した頭が働かない人のログ

※コンテスト中に考えまとめるために書いているので人に読ませるために書いてません。誤字とか誤変換とかは後で読むように多少訂正してます。


A問題

Bを押すタイミングは始めと終わりだけっぽい。 全パターン2*2=4やってみるか

通った。

B問題

マスが負の値を持つことに思い至らなくて、しばらく?マークついてた。

塗る回数に制約ないから最終的にどんなふうに濡れるか考える問題っぽそう。

Kの連なりが必ず1つは出来るけどそれ以外は自由っぽい。

なんか本当にそうか分からないけどそれなら初めからN個色塗ってそれ以外+なら黒でーなら白に塗るのを全部探索すればN*Kでいけそう

一つずらすたびに、ずらした分だけ足し引きすればNでよくない?

サンプル合わない

繰り返し回数をK-Nにしてた なぜか白く塗ったところを0ではなく符号反転して加算してた。なんで?

サンプルあった。通ると良いけど……。

通った

C問題

テトロミノみただけで面倒くさい問題っぽい感じがする。

縦は2マスだけなので同じところにずっと積んでいく感じかな

なんか飛ばしたほうがいい問題っぽそうだと思って順位表見たら赤数字沢山ついてたので一旦D読もう。

D問題

問題文が読めない

なんとなく読めた。数字IがI番目に出てくる番地が数列XのI番目の数字と同じになればいいのか

Xの順番は判定では意味なさそう。I番目にでてくるのが必要なんだからいるわ

とりあえずXで決められてる番地に数字を固定する。 Xの数字が小さい(Aの先頭に近い方から)方から順に条件満たすように前に詰める形で数字いれていけばいい?

とりあえず、これで行けそうだからこれでいく。

集中力切れてる。言い訳すると部屋が暑い。

とりあえず矛盾しないように埋めることはできたんだけど、後ろ側の0が埋まらない。残ってるので適当に埋めればいいか。

Eclipseが固まりかけた……。

-1に初期化してたとこ更新されない場合見落としててエラーなってた

後半ほとんどREとWAだった……。

REは前に詰めてたら足りなくなってXIこえちゃったとき確かめるのがきちんと判定されてなかったからっぽい。WAはしらないあと5分じゃ無理そう。(だいぶ頭働いてない)

とりあえずWAには変わった。ここから考えるのは無理そう。

半分ぐらいWAなので多分根本的なこと見落としてる。


コンテスト終了

本来ならDの最初当たりでやめてた気がするけどコレ書いてたからやめなかった気がする。書いてったほうがいいな。

集中切れてから明らかにIQが3程度まで落ちてるから集中切らさない方法が必要。

Cこっち解いてたほうが行けた気がする……。

DはIQ3状態では多分どうしようもなかった。

D解こうとしてるけど、前から埋めたことを忘れて後ろから埋めようとしてたのでまだ頭働いてない。

WAはへったけどWAが取れないしこれ以上思考が持たないので終了。

提出

http://agc008.contest.atcoder.jp/submissions/all?user_screen_name=kiki33