捏造スターの心得

Q. これはなに？

A. ととりにゃあ アドベントカレンダー 9日目の記事だとおもいます。adventar.org

 

こんにちは、毎日コンテストと申します。

本記事では「捏造スターの心得」について話します。

 

捏造スターってなに？

まじでなに？

このSnukeさんのTweetが発端っぽい　へぇ～

捏造が横行し始めてからまだ1年しか経っていないらしくびっくり

ここから人としてふざけてる競プロer達が人の記事に捏造スターを付け始めることになります。

捏造スターが作れる条件
  1. 記事中の文字列を連結したものを $S$ とする
  2. $S$ から何文字か取り出して元の順番で連結した文字列を捏造文字列としてスターで引用することができる

　もう少し条件は緩いっぽいが分からん

捏造スターの作り方

ブラウザはChromeを想定しています。（FIrefoxだと楽らしいがChrome信者なので言及しません　ぐーぐる様最高～）

  1. 捏造しまくりたい記事を開く

    例としてこの記事を開いてみます。
    nrvft.hatenablog.com

  2.  適当な文章を右クリックして検証を選択

    f:id:nrvft:20211209171841p:plain

    記事の末尾で検証を開いた例


  3. 右のデベロッパーツール画面で捏造可能な文字列を入力
    元の記事画面に捏造したい文字列が生えます

    f:id:nrvft:20211209172513p:plain

    オタクが大好きなデカい数字で捏造


  4. 文字列を選択してスターを付ける

    f:id:nrvft:20211209172805p:plain

これで君も捏造マスターだ！

 

続きを読む

AtCoder 黄色と申します

2021/06/06(日)のAtCoder Beginner Contest 204で黄色になりました！ 嬉しいね

 

AtCoderのレート推移はこんな感じ

 

112回もratedコンテストに参加してるのすげ～～～～～～

コンテストに初めて参加したのが2019/02/16なので、いつの間にか2年4か月も競プロをやっていたらしい

 

【感想】

黄色は競プロを始めた当時からの大きな目標だったのでかなり嬉しい

今年中に黄色になりたいと思ってたので達成できて本当によかった

競プロ始めたての頃は暖色がバケモノ集団で遠い存在だと感じていたので、自分がそこまで来れたと考えると特大クソデカ感動

次の競プロの目標はICPCで良い結果を残すことなので頑張りたいね

 

【精進】

AtCoderのAC数はこんな感じ

Streakが切れてから土日だけ競プロをするカスになってる毎日コンテストさん

各種サイトのAC数を合わせるとこんな感じ

 

最後にレートを黄色まで上げるのに役立ったと思う精進を挙げます

  • ABC埋め

 多分これが一番役立ったと思います

黄色になるにはABCで勝ち続けるのが理想で、よく見るタイプの問題を早解きできるようになったのはABCを埋めたおかげだと思います

事故による下振れを避けるのにも役立ってくれるはず

↓ う笑 

  • 水埋め・青埋め

このあたりのdiffを解けるようになると青パフォ、黄パフォが出せるので嬉しくなる

  • ライブラリ整備

青色相当のライブラリは大体用意してるはず

ライブラリがあるとないとでは問題の解きやすさがかなり変わるので色々用意したほうがいいです

人様のライブラリを借りるよりも自分で一から真心をこめてライブラリを作るのがおすすめです（温かみがあるのでより暖色に近づける）

 

E8さんの典型90もおすすめです　自分もそろそろ埋めないとな...

 

おしまい

AtCoder Heuristic Contest 001 参加記

 

ついにレーティングがつくマラソンコンテストがAtCoderで開催されました。嬉しいね

マラソンコンテストにがっつり参加するのは2020/11のこどげオババコンぶりで2回目になります。

 

問題概要

問題ページ

$ 10000 \times 10000 $ のスペースと $N$ 個の広告に関する座標 $(x_i+0.5, y_i+0.5)$、面積 $r_i$ が与えられる。各広告は与えられた座標を内包するような長方形であり、広告どうしが重なってはいけない。$s_i$ を $i$ 番目の広告の面積として、以下の式により定められたスコアを最大化するような広告の配置を決定せよ。

\[ score = \sum_{i=1}^{N} \left( 1 - \left( 1 - \min(r_i,s_i)/\max(r_i,s_i) \right)^2 \right) \]

 

結果

 

最終的な順位は50位でした！！！！（順位賞が欲しい）

最後の2日間で4909から4938まで上げられたのがデカ過ぎました

 

※2021/03/18 追記

コンテスト終了後のシステムテスト後の順位は49位でした！
パフォーマンスは2268でマラソンのレーティングは1268になりました
マラソン水色と申します

 

方針

　全体の流れとしては、山登り法を主軸に置いて、ヒューリスティックな操作を考えては追加、考えては追加・・・と繰り返していました。当初は焼き鈍し法で取り組もうと考えていたんですが、温度設定がよく分からずスコアが微妙になってしまっていたので途中で山登りをすることにしました 🗻。

 

以下に最終提出で使った操作を書いていきます。

 

- 土台の部分

まず、$10000\times 10000 $ のスペースを全部持っておくわけにはいかないので、どうすれば効率よく広告どうしの隣接判定や、広告の伸縮ができるかを考えます。自分の実装では、x1, x2, y1, y2毎にunordered_setを10001個ずつ用意して管理することにしました。これにより、広告の大きさを変えた際の座標の追加・削除や隣接判定が容易に行えました。広告の伸縮に関しては、幅を±1したいときは隣接面を参照して、可能な限り伸ばしたい場合は+1ずつ伸ばすのではなく、他の広告との衝突判定をして決定します（中盤まで+1ずつ伸ばしてたけどこっちの方がずっと速かった）。

 

- expand

各広告の面積を可能な限り広げます。

別の広告と隣接していない場合は+1して、隣接している場合は他の広告を押すことによって+1だけ広げられるかチェックしました。

queueで順に広告を見て、改善されたならまたqueueに突っ込むことを繰り返すため、まんべんなく広告の面積が広がってくれます。

 

- corrade

ある広告の幅を-1して、その広告と隣り合った広告を+1して改善されるかチェックします。

この操作が多分MVPで、スコアにかなり貢献してくれてました。これもqueueで更新フラグを立てて操作を繰り返します。小さく押し込まれていた広告は大体これで解決されているはずです。

 

- reset_one

 ある広告を $1\times 1$ にリセットして、4方向に対する24通りの全探索で可能な限り伸ばすことを繰り返した後、元から最も改善されたものを採用します。

正直なところあまりスコアに寄与しなさそうだと思っていたんですが、この操作が選ばれる確率を小さくするとスコアが目に見えて下がっていたので、最後まで使っていました。

 

- reset_neighbor

 ある広告と隣接する全ての広告を $1 \times 1$ にリセットした後、最初の広告から優先的にreset_oneを行います。

スコアの小さい広告ほど選ばれる確率が高くなるようにしています。ガチガチに固められて動けなくなっている状況を打開するのが目的です。reset_oneが終わった後は更なる改善の余地があるはずなので、expandとcorradeも適用した後の全体スコアが改善されたかチェックしました。

 

- penetrate

 ある広告を$1 \times 1$にリセットした後、選んだ方向に進んで突き当たった広告を手当たり次第に$1\times 1$にリセットしていきます（破壊神）。

これもスコアの小さい広告ほど選ばれる確率が高いようにしています。

reset_neighborでは網羅できないような複数個先の広告まで固められている状況を打開するのが目的です。面積を十分大きくできるまで破壊を終えたら終了します。

 

- change_side

ある広告と隣接している別の広告をランダムに選択して$1 \times 1$にリセットした後、隣接面と異なる方向に優先的に広げます。例えば上下に隣接している2広告は 横の面で隣接しているはずなので、リセット後に縦向き→横向きの順に幅を広げていきます。

局所解にはまっている広告間の関係を変えるのが目的です。

これ全探索していたのでかなり重くて、1/100 で選んでたけど2000msとか3000msとかかかってました。全体のスコアにはある程度貢献してました。

 

- adjust_1

全操作の最後に広告の幅を±1だけ調整します。各広告について$x, y$の一方を+1、もう一方を-1することを改善されなくなるまで繰り返します。

これは最大長方形問題を解くのが理想で、頑張れば1広告あたり $O(N)$ で解けるはずなんですが、サボりました。かなり後悔してます

 

- adjust_by_stretch

スコアが小さい広告から、強制的に各方向に幅を+1してcorradeを適用することを繰り返します。

$r_i$ と $s_i$ の差が大きい広告絶対許さないマンとして機能してくれることを期待しました。

これは最終日に考えたもので、そこそこの確率でこの操作を選択するようにしたらかなりスコアが伸びてくれました。最高

 

 

 

おわりに

この9日間ずっと楽しんで取り組むことができました。設定はシンプルだけどマリアナ海溝より奥が深い問題で非常に面白かったです。

ヒューリスティックな操作をたくさん並べただけの山登り法でも高順位を達成できたのは嬉しいですね。他の方々とは違って手数で殴るような方針を取っているので、こんな戦略でもそれなりの点を取れるんだなと参考になれば幸いです。

上位勢の感想をパーッと見た感じだと、焼き鈍し+α の方針が多かったので、もう少し焼き鈍しを考えてあげるべきだったかもしれないです。面積を $r_i$ より多少小さく見積もってもスコアの損失が少ない性質ももう少し活かすべきだったと思います。

改善点をいくつか残したままコンテスト終了を迎えてしまうのはかなり勿体ない気がするので、次回はアイデアを試しまくりたいね

 

AHC002も出るぞ出るぞ

CODINGAME FALL CHALLENGE 2020 参加記

 はてなブログ初投稿媼、名を小竹と申します...

www.codingame.com

CodinGameで2020/11/13から2020/11/23にかけて開催されていたFALL CHALLENGE2020に参加しました。

マラソン形式のコンテストにがっつり参加したのは今回が初めて

序盤

 周りの人々が参加表明をしていたので、流れに乗って参加

tsukammo.hatenablog.com

 ツカモさんがルールを翻訳して宇宙一わかりやすい記事を出してくださったので、すんなりとルールを理解することができました。

ただ、こどげのデフォルトのINPUT処理がかなり分かりづらくて最初何を受け取っているのか理解するのに時間がかかってしまう（そうでもない？）

とりあえずWood2とWood1ではルールがシンプルなので、簡潔なコードで改善を試みます。

 無事BRONZEまでたどりつくことができました。

この段階でインベントリ・魔法・ポーションのクラスを作って、dfsで生成することが可能なポーションを探すといった実装をしていました。

中盤

 3日後にスキップします　こどげを触っていませんでした（何？）

 とりあえずWood1のときのカスdfsから実装を変えていなかったのでいじります

 ここでインベントリのすべての状態が $_{14}C_4 = 1001$ 通りしかないことに気づきます。

そこで10個の手持ちの状態を4つの1で区切って 01000100010010 のように14bitで符号化してあげます。右（最下位ビット）からtier0,1,2,3, 空のように管理します。

これで 0100001000100 ⇔ {1, 2, 3, 3} のようにインベントリの状態を整数値で表すことができました。

1ターン50msといえど、頂点数が1001通りであれば適当にBFSかdijkstraしても余裕で間に合いそうなので実装しました。

 

 急ピッチで実装したので案の定バグります。

この時点では、RESTとrepeatableを考慮せずにBFSで必要ターン数を計算しています。

なんとかデバッグしてBRONZE内でもいい感じの順位に落ち着くことができました。

 11/16 02:00にSILVERランクが解放され、すぐに昇格することができました（嬉しい）

 人の泊まりにいき、家主が寝ている中こどげをしていました（は？）

このあたりからコード改善を試してもうまくいかないことが続きます。

 11/19 02:00にGOLDランクが解放されましたが、到底辿りつけそうにない状態でした。

  • （敵の行動を考慮しなければ）REST込みで正確な最小ターンを得られるようなdijkstra法を実装
  • LEARNで得る魔法は消費する素材、生成する素材のうち、手に入れてない組合せを優先
  • ポーションの獲得戦略を現在までの獲得個数に応じて変更

上記のような改善を追加しても目に見えて強くなることはありませんでした。

RESTとrepeatableを考慮したdijkstra法がかなり重かったのもあって、たまにTLEを起こしてしまうのも良くなかったです。

終盤

有効な改善案を探すために、強い人の婆の行動を観察していたところ、1つのポーションを作成した後も一定数素材が残っていることに気づきます。

そこで、ポーションを作成できる条件に付加価値の概念を増やしてぴったり素材を消費することが無いように変更しました。

 

 この変更がかなりうまく作用してくれました。

 この調子でLEGENDも目指そう！と意気込んだものの、Link044が強すぎる

 2ターン毎にポーションを作成する行動は僕のおばあちゃんには出来ません・・・

 最後のあがきで#pragma GCC optimize("O2") をしてみたところ、10倍くらい高速化されました（マジ？）

 そこで、時間がネックとなって試せていなかった 1個目のポーションを取った後、2個目のポーションまでの必要ターン数まで計算する処理を実装しました。

ちょっとだけin ARENAのコードより改善できたっぽいので提出して最終日は就寝

 結果は全体210位（ゴールド内130位）でした。

マラソン系コンテスト実質初参加だし、かなり満足しています。

反省点

戦略らしい戦略としては、dijkstra法で必要ターン数を求めたことくらいなので、ゲームAIらしい探索をしてなくてかなりもったいない気持ちです。

Twitterでよくみる人々はビームサーチやChokudaiサーチを上手く駆使していたので、スゲ～～～～～～～～～～～～～～～～～って思いながら眺めてるだけだった

AtCoderでもマラソンコンテストが更に生えてきそうなので、マラソンの基本戦略やアルゴリズムを勉強したいね

次回の目標はLEGENDに行くことです　頑張るぞ

おまけ

 ところで錬金術といえば、12/3(Steam版 1/26)にライザのアトリエ2が発売します！

アトリエシリーズをやったことない人、まずはライザのアトリエ1をプレイしてみよう！

かなり面白いです