2019-12-18

HTTF2020本選参加記

この記事は、NITKC Prolab Advent Calendar 2019 の17日目の記事として書かれています。

前日は宮野さんの記事です。

まえがき

とばりといいます。
最近は友人が思いついた問題(有名な未解決問題だった)に軽い気持ちで挑んでいます。解けるかなんて知りません。
それはそれとして今年は8月からほぼ一か月に一回のペースでオンサイトコンテストに出向いているんですよね、焦点の定まらない生活を送っています。
今回は、その中でも、12月7日に行われたHack To The Future 2020 本選についてお話します。

HTTF

予選と本選があるマラソン形式の8時間コンテスト
予選問題 : HACK TO THE FUTURE 2020予選 - AtCoder
本選問題1 : HACK TO THE FUTURE 2020 本選 - AtCoder
本選問題2 : HACK TO THE FUTURE 2020 本選 2 - AtCoder

日記

本選は12/7(土)に東京で行われたのですが、僕は福岡県にいつもいるので
12/6(金)旅立ち
12/7(土)本選
12/8(日)帰宅
みたいなスケジュールにしました。
これはあたりまえなのですがあたりまえのような金曜日の授業は欠席されました。

1日目

旅立ちの日

pic.twitter.com/aTx1KSiMRD
— とばり (@toritobaritori) 2019年12月6日

飛んだ

これは前日の脳内

明日東京、どこ行こうか
— とばり (@toritobaritori) 2019年12月5日

秋葉原に行ってください、次にヨドバシカメラによってください、そのあと東京タワーに行ってください。
こんな声が未来から聞こえてきました。

秋葉原に行きました。ここで！ラジオ会館を登っていると、†ドルフィードリーム†というどこかで見た文字が！！！　偶然です。運命でしょうか。
ドール界隈についてはぜんぜん知らないのですが、実は少し前からドールに何かを感じて一から紙粘土で作ろうとしていた友人がいて、ドールの文化に初めて触れたのはその辺です。
ドールって、フィギュアとは違って関節が動いたり、目は眼球を模していて、人形に生命が宿っているように感じるところがとても魅力的なんですよね。思わず写真を撮りたくなる。。。
ドール、、、いつの日か、、お迎えしたい。。

次ですが僕は今回デジタル一眼レフを持ってきていまして、NikonのD3400なのですが、、このレンズをいろいろ見たいとのことでヨドバシカメラによりました。
やすくて5万、ぼくは何をしに来たのだろう...

このあと東京タワーによったのですが、外観はとても美しい、しかし、入ってみると低い、東京タワーは外から見るものなのでしょう。

2日目

本選当日です。
朝は早く起きてお食事券を使用して朝食を食べて元気を出します。本選を頑張る決意をしました。
雨の中、傘もなく、道に迷った末、無事集合場所にたどり着きました。

上と下は趣味に書くべき内容なんですがここでプロの内容を書きます。
(これは技術要素ですか？いいえ)

本選

今回の本選では、作問ミスがあり、8時間マラソンが4時間、4時間のダブルマラソンとなりました。それぞれのコンテストで僕がどんなことをしたのかを書きます。

問題の概要

xy平面上のN個のノードの集合Vと、S個の木Tiが与えられる。
Vにおいて与えられたノード間にはノード間の距離がある値以下であれば辺を張ることが可能。与えられたS個の木のそれぞれのノードとVのノードを対応づける。
このときできるだけグラフと木がマッチする(Gの無駄な辺が少ない)ような辺の貼り方とノードの対応づけを行ってください。

コンテスト(問題1)

最初に実装したのは以下のようなものです。

まず、Vで張れる辺はすべて張っておきます。ここでできたグラフをGとします。
Gから平面の真ん中近くにあるノードを選択します。
次に、Sから入力順に木Tを一つ選択します。
Gから選んだノードを木Tの根に対応付けて、Tに従ってGをDFSして、TとGのノードの対応付けを行っていきます。
ここで、各Tに対して同じGの頂点からDFSを行っていきました。ノードの被りや辺の被りも全く気にしないコードをまず書いて、TがGにそもそも埋まらない場合はエラーとしてお祈りのコードを書きます。
最後に使わなかった不要な辺をGから削除します。
ここで初の提出を行いました！！

迫真の！　0点！！！

だいたい予想どおりの結果でWAが出なかったことに安心します。
(なんかこの時点で2時間たっていてなんと満点が数人。実装力ダメです。頑張ってください。)
この辺でchokudaiさんがやってきまして、コンテストが二分割されることが決まりました。

ここから満点を目指して実装を頑張ります。
次は、それぞれのTの根に対応付けるGを乱択しながら頑張ります。
適当に出してみると、95万点が取れました。うれしい。

しかし、これ以降点数は上がりませんでした。
バグなどと戦った末、やり残したことがたくさんでした。

コンテスト(問題2)

問題2は問題1の制約拡張版でした。
木のサイズが大きくなって可変となり、辺の制約が少し厳しくなりました。

本番はここからだ！と気合を入れて実装をしました。
といっても問題1のコードにやりたいことを追加していくだけです。
実装したのは以下のようなアルゴリズムです。

Gのサイズに対して木のサイズが大きくなったため選んだ根によってはGとTの対応付けができない場合があるー＞あるノード(子)から先が対応付けできないならば、DFSバックトラック時に対応付けをもとの状態に戻して、次の子で試す。
木単位で根を選びなおして対応付けを変更し、スコアの上昇があったときにそれを採用する山登り。＜－あまりぎりぎりの制約でなさそうだったので貪欲で十分強そう。 Tの各ノードにおける子の順番の変更(山を登りきってそうなときに)。

これらを実装しました。しました。したはずでした、、、、、
点数が、、、27万点、、、、、

結局これ以上伸びませんでした。
対戦ありがとうございました。

点数が伸びなかった原因(バグ)

僕がバグ埋め小宮になっていたことが後日になって分かりました。
どんなバグ？
一度バックトラックが起こるとTがGに埋まらないという判定になって根の変更まで戻ってしまうというバグです。
バックトラック時の判定が親を通り越して伝わっていたんですね。

まぁ時間もなくて焦っていたのもあるんですがDFSのバックトラックにおける勘違いはここだけの話ではなく無限回起こしたことがあるのでいつも気を付けています(気を付けています(素振りしています(素振り！)))

本番では素振りしましたが(ア！)

これ、JOI本選でも同じようなことをして春を逃しています。お疲れさまでした。 (WAの光景が目に焼き付いて離れませんたすけて)

懇親会

懇親会ではとてもおいしい料理が無限にわいてくるテーブルが用意されていて、たらふく食べさせていただきました。ごちそうさまでした。
主にユースの人々と競プロのことについてや本選問題についてなどの会話をしました。楽しかったです。

三日目

朝食、TLEしまして、秋葉原にもう一度ドールと音楽機器を見に行きました。
技術書同人誌など売ってるところにも行ってみて回りました。

ここでたべたのは朝食兼昼食

retty.me

おいしかった。ただ朝食兼昼食にはちょっときつかった。

その後、小説読みながらフライトをしました。

博多に戻っての夕食
博多駅周辺を歩いていたら神のような店を見つけ、即決で食べました。
👼おいしい.......

tabelog.com

しろごはんのやさしい甘さがわかる人はみなさんここに行ったほうがいいと思います。

こうしてHTTFの旅が終了しました。

あとがき

遅刻しました。ごめんなさい。
睡眠の誘惑にはどうやっても勝てなさそう。

これでとばりのAtCoder初オンサイト参加記を締めさせていただきます。

次の日の担当はhunachiさんです。

2018-12-17

ここ半年でホームポジション矯正して平均程度のタイピング速度を手に入れた話

この記事は久留米高専プロラボ部 Advent Calendar 2018 の 12月17日の記事として書かれています。

https://adventar.org/calendars/3099

はい

とばりです。
タイピング速度、プログラマや情報系（の限りではないが）にとって重要ですよね。
なぜかというと、それが速いだけで効率が確実に上がります。
また、プログラマには効率厨、比較的多いとの噂を耳にしたことがあるのでタイピングを極めるのはそういう人たちにとってはうってつけでしょう。

本題

本題ですが、僕が半年何をしてきたのかというと、
nkn先生の勧めるとおりこのe-typingというサイトで適度にタイピングをしていました。
今回は僕が約半年でタイピングを少しだけ意識してみたことで思ったことなどを書いていきます。

単刀直入に言ってしまいますが
基本的にはこのサイトでタイピングした後の画面などに現れるコメントに忠実になることをお勧めします。
まぁこれだけじゃ完全に投げやりなので自分なりに流れをまとめてみました。

手順

まず手始めに会員登録をしておきます。その後、

基礎練習をやってホームポジションを覚えてゆっくりブラインドタッチ。
基本練習、応用練習で短文を正確に打てるように。
今日の指トレをやってA以上を出した後に†腕試しレベルチェック†。
ホームポジション意識しながらプログラミング。
†チューニング†。

こんな感じでしょうか。

とりあえず1.をやります。慣れるまでやります。まずは1.で停滞しましょう。
2.も1.と同じ時期にやってもよいと思います。
僕の場合はこの時期はほとんど毎日競プロをやっていたので2.くらいまでは自然と慣れました。

ここで注意ですが腕試しレベルチェックは慣れないうちはあまりやらないほうがいいかなと個人的に思っています。
このチェックでは一文だいたいアルファベット15文字が15文くらい降ってきます。
つまり、およそ225文字。これがなかなかつらい。
そのため、遅いうちは一回終わらせるのにINF時間かかり、ミスも増えるので楽しくないです。

それでも最初にほんの少しミスなく丁寧にやっといてカルテに登録しておくことで後から自分の成長がうかがえてよいかもしれません。
*1

たまぁ～～に腕試しレベルチェックをやって150WPMだせる、
または寿司打の3000円コースでもうちょっとで得をする
くらいになってきたあたりから腕試しレベルチェックをやりこんでみるとうまくいくかなぁと思います。

そして4.でプログラミングをするいい点として、打ちにくい記号に対処できるようになります。

要するに、1.、2.を最初はやりこみ、慣れてきたら3.、4.をやります。
実際こんな感じでやりました。

そしてミスをしないことを頭に叩き込んで速度なんて気にせずに腕試しレベルチェックをやります。

そうするとミス数とタイピング速度が均衡を保ちながら、ゆっくりとだんだん上がってきます。
これは結構面白くて、今までは考えて打ってたキーがノータイムで自然と打てるようになってきます。
不思議な感じです。「いつの間にか打ってる」みたいな
コツとしては文の途中でも、「ちょっと打ちにくい」というような節が出てきたらごり押しをせずにちゃんと止まって打つ感じです。

そんなこんなをしているうちに簡単な文は滑らかに打てるようになり、少し詰まろうともちゃんと止まってミスなく打てるようになることができました。
これくらいでA判定に手が届くようになります。

たまに詰まるやつをもう少し慣れると多分Sも狙えるんじゃないかと思ったりしています。
あと小指の出張（ハイフンなどそこら辺）はかなり大事だと思うのでその感覚も鍛えていきたいところ。
（出張というとjubeatみたいですが思い切って出張させていけ）

5.、チューニングですが僕にはまだまだ達することのできない境地です。Sより上の修行僧の話です。

まとめ

ミスと速度の均衡をうまく保ちながらやりましょう。
とりあえ丁寧にやりながら続けることでAにはたどり着けることは保証します。
感覚と集中力を養っていきましょう。

終わり

最後に僕の平均的なカルテを見て癒されて終わってください。（ランキング登録者の平均（詳しくはしらない）なので悪いものではないと思っていますがAはまだまだ遅いですね。）

†S†以上の人もクラスに何人かいるようですが実力を隠蔽するので
僕のクラスにおいてA以上の人がいないことになっているのがおもしろいですね。

A行ったら平均超えるんですね
いいですね pic.twitter.com/Hd04v0ujS8
— とばり (@toritobaritori) 2018年12月14日

なんか見返すと当たり前のことを言っていて面白いですね。

明日は05さんです。それと、11日更新予定の鈴木君の記事には期待しておきましょう。

*1:カルテには腕試しレベルチェック後の画面の右下にある登録というところを押すことで登録できます。

2018-08-13

JOI 2011 春合宿 day1-1 横断幕(Banner)

問題文
https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf

解法
部分点
対角する2点を決めれば長方形は決まるので全探索をすると部分点がもらえます。 $O(H^2W^2)$

満点
まず2列を決めます。すると長方形のすべての頂点がその列に含まれることがわかります。
また、2列が決まった状態で行を二つ決めると長方形ができます。ここで、二つの頂点の色の組として、ある一行にある $(C_1, c_1)$ 、別のもう一つの行にある $(C_2, c_2)$
を考えることができます。
この頂点の色の組は6パターンの、 $(0, 0)$ , $(0, 1)$ , $(0, 2)$ , $(1, 1)$ , $(1, 2)$ , $(2, 2)$ が考えられます。(色の順序は問いません)
そして、すべての2列の組に対してのそれぞれの頂点の色の組の個数がわかっていれば四本の柱の選び方の個数が出てきます。0, 1, 2 がそろっていればいいため、
これは

((0, 1)の個数) * { ((0, 2)の個数) + ((1, 2)の個数) + ((2, 2)の個数) } + ((0, 2)の個数) * { ((1, 1)の個数) + ((1, 2)の個数) } + ((1, 2)の個数) * ((0, 0)の個数)

をすると求めることができ、これをすべての2列の組に対して求めました。
$O(HW^2)$

下のコードでは頂点の色の組をbitで表現しています。
0番目のビットが立っているときにはその頂点の組には黒がある。
1番目のビットが立っているときにはその頂点の組には灰色がある。
2番目のビットが立っているときにはその頂点の組には白がある。
というようにし、例えば(黒, 白)を(b, w)と表現し、bitの状態は 101 (= 5)としています。

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef vector<int> VE;
#define int long long
#define INF 1000000009
#define INFL 1000000000000000018
#define mod 1234567
#define pb push_back
#define MAXN 1003
#define bb 1
#define gg 2
#define ww 4
#define bg 3
#define bw 5
#define gw 6
 
 
int h, w, fid[500][500], ans, res;
 
signed main()
{
    cin >> h >> w;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> fid[i][j];
        }
    }
    for(int i = 0; i < w - 1; i++){
        for(int j = i + 1; j < w; j++){
            int bit, sum[7] = {0};
            for(int k = 0; k < h; k++){
                bit = 0;
                bit |= ((1 << fid[k][i]) | (1 << fid[k][j]));
                if(bit == bb){
                    sum[bit]++;
                }
                else if(bit == gg){
                    sum[bit]++;
                }
                else if(bit == ww){
                    sum[bit]++;
                }
                else if(bit == bg){
                    sum[bit]++;
                }
                else if(bit == bw){
                    sum[bit]++;
                }
                else if(bit == gw){
                    sum[bit]++;
                }
            }
            res = sum[bg] * (sum[bw] + sum[gw] + sum[ww]) + sum[bw] * (sum[gg] + sum[gw]) + sum[gw] * sum[bb];
            ans += res;
        }
    }
    cout << ans << endl;
 
    return 0;
}

蚊帳のーと

日々日々