2020-12-18

AtCoder で黄色になりましたか？

色変記事AdventCalendarを作成しました。
みなさまの勇気ある宣言をお待ちしております！https://t.co/1NqMxq7Wu3
— dokin (@ayoiyouyoeyo) 2020年11月4日

この記事は色変アドベントカレンダー 2020 の 18 日目の記事です。
17 日目のももはらさんの「色変（できませんでした）記事 - ももはらの日記」から、19 日目の tomerun さんの「AtCoder（ヒューリスティック）で何らかの色になれませんでした - TopCoderの学習のお時間」という記事へと続いていきます。

この記事は「AtCoder で黄色になりましたか？」という問題の解法について記述します。

・問題概要

AtCoder のアカウント ID が与えられるので、レートの highest が黄色に達している場合は "Yes" を、達していない場合は "No" を出力してください。

・解法

python による解法を紹介します。urllib でページを取得し、lxml でパースしてレートの highest を取得します。この値が 2000 以上の時に "Yes"、そうでない時は "No" を出力すればよいです。

・実装例

# -*- coding: utf-8 -*-

import urllib.request
import lxml.html


def main():
    user_id = input().strip()
    contestant_url = f"https://atcoder.jp/users/{user_id}"
    html = urllib.request.urlopen(contestant_url).read()
    html_tree = lxml.html.fromstring(html)
    highest = html_tree.xpath("//table[@class='dl-table']")[1]
    highest = int(highest[2][1][0].text)
    if highest >= 2000:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

・結果

$ python get_highest.py
kawara_y
Yes

やったぜ。

・黄色になるために

黄色になるまでにやったこと：問題を埋めて色々なアルゴリズムを知る。
以上です。ご参考になれば幸いです。

・後記

xpath で取得した後がかなりダサくないですか？綺麗な方法を教えてもらえると嬉しいです。

2020-06-15

AtCoder で 2 回目の青になるまで

AtCoder で 2 回目の青を果たしました。前回青になってからやったことをここに連ねます。

AGC で競技 First CE 勝負に参加する

AGC などでは、NoSub 撤退してしまうことを自分に許さないために、コンテスト開始直後に CE となるコードをジャッジに投げることが流行っています。僕もそれをしている一人です。

みなさんは AGC44 と AGC45 を覚えていますでしょうか？僕は覚えています。
競技 First CE に負け、さらに 0 完太陽をキメた僕はレートを溶かしました。

ABC に参加する

ABC に参加し、いいパフォをとることでレートが向上するらしいです（※これは個人の感想です）
ABC170に参加することでレートが上がり、青に戻ることができました。

以上です。

2020-05-01

AtCoder で青色になりました

f:id:brokentile:20200430121733p:plain

タイトルの通りです。2020/4/26 にAtCoder 青色になりました。水色になったのが 2019/7/7 なので約 10 ヶ月かかりましたね（長かった……）

一応変色記事として何かしら書き残しておきたいと思っているのですが、勉強したこととかは本当にちょっとしか覚えてなくて書くことが思いつかないため、とりあえず水色になってから青になるまでに何があったかをかいつまんで書いておきたいと思います。

水色になってから（上の画像の①から②まで）

特に何もないです。通学のために電車に往復 3 時間くらい乗っていたので、電車の中でせっせと過去問を解いていました。その結果かどうかは分かりませんが、ある程度の早解きが出来るようになってレートが上がっていきました。この時の Highest が 1499 で、まさかこの先スランプに陥るとも知らずに「あと 1 で 1500 なのに惜しい〜〜笑」とか言ってました。呑気で面白いですね。

スランプ期（上の画像の②から③まで）

②の時くらいに引っ越しをして学校の近くに下宿を始めました。環境が変わったからなのかは分かりませんが、問題が解けなくなりました。本当に本当に本当に本当にかなり精神的にしんどかったです。

Re: 1288 から始まる競プロ生活（上の画像の③以降）

何か機転があったようにも思えませんし、色々あったようにも思います。

あったことの一つは DDCC 2020 本戦に参加したことです（DDCC 2020 参加記 - かわらにかわらは割れない）chocobo さんやばくさん、snow くん、ふっぴーさん、Akira Ajisaka さんとお話ししたりしました（正直この時モチベが下がりすぎて参加を辞退しようかめちゃくちゃ悩んでいたのですが、T シャツを頂くために参加し、結果的にはモチベの回復に繋がりました）
他には、あさかつに参加し始めました。あさかつは、水コーダまでにとっては早解きや復習の役にかなり役立つと思います（経験談）また、けんちょんさんの蟻本記事（AtCoder 版！蟻本 (初級編) - Qiita）やE869120 さんの記事（レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita）の問題を解いたりして、典型をちゃんと解くための力を付けようとしたりしました。
また、codeforces で紫タッチしました。これもモチベ回復の一端を担いました。
さらに、AtCoder の所属を「う　し　た　ぷ　に　き　あ　王　国　笑」に変えました。レート遷移を見てもらえば分かりますが、変えた後のコンテストからレートが上がり始めました（今は出国してしまったため、所属はう　笑ではありません）

今の自分に関してこれまでと変わったなと感じていることとして、これまでずっと数え上げと DP に対してめちゃくちゃ苦手意識を持ち続けていたのですが、多少は手が出るようになったことが挙げられます。何でなんですかね、僕には分かりません。

最後に

お世話になった人たちに感謝を捧げます。特に、そもそもの競プロを始めるきっかけとなったきゅうりさん、分かりやすい解説記事を公開しているけんちょんさん、アルメリアさん、ライバルのスギノキさんやぷちくん、凸守さん、けーむさん、lemon さんたちにはとても感謝をしています。本当にありがとうございます。

2020-02-14

Codeforces で紫色になりました

TL; DR
受験生競プロ er には大阪大学をオススメしておきます。

f:id:brokentile:20200214105336p:plain
タイトルの通りです。紫色になれました。現時点で AtCoder のレートが 1313 なので差は約 600 あります。楽しいですね。

栞代わりにブログを書いておこうと思います。最初に断っておきますが、誰かの参考にしてもらうようなことは書けないので読むのは時間の無駄です、ごめん。

やったこと

引越し：大学近くに引っ越しました。やっっっと煩わしい満員電車から解放されました。生活リズムは破壊されました。

恋愛：彼女が出来ました。これは自慢です。

競プロ：Div. 3 のバチャをたくさんやった気がします。アルゴリズムの勉強もした気がしますが、その時その時の気分でググって調べてたので何を勉強したのかは覚えていません。

オンサイト参加：KUPC や DDCC2020 に参加させていただきました。オンサイト参加はモチベがあがりますね。

これから

DP と数え上げへの苦手意識をなくす。

グラフに関するアルゴリズムを勉強する（楽しいので）

受験生競プロ er に大阪大学をオススメする。オススメポイントはここには書ききれないので、僕かじゅぴろくんに「話聞かせろや！」っていうとご飯くらいなら奢ってもらえると思います。

2020-01-26

DDCC 2020 参加記

DDCC 2020 本戦に 21 枠で参加しました。本人は般若枠で通ったと思い込んでいるようです。

DDCC 般若枠です、よろしくお願いします！ #ddcc2020 pic.twitter.com/z1OgFeyzCI
— かわら (@kawara_y) 2020年1月25日

本戦前日

当日始発で行くつもりだったのですが、朝の時点で寝坊する未来しか見えなかったためホテルを予約しました。もうちょっと早めに危機感を持ってほしくないですか？僕は持ってほしいです。

本戦当日

昔の偉人が言っているように [要注釈]、崩れた生活リズムは急には戻せません。全然寝れませんでした。しかしちゃんと起きれました。偉い！

chocobo さん僕の横空いてるよ！
— かわら (@kawara_y) 2020年1月25日

chocobo さんに Twitter で呼びかけると反応してもらえて、隣同士で座りました。知ってる人がいて安心です。

開始まで雑談をしていたのですが、ここで AtCoder ID を最近変えたせいで順位表に僕の名前がないという事実に気付きました。
そこで chokudai さんを探し、「最近 ID を変えたからか順位表に名前がありません🥺」と伝えたところ、対応してもらえました（そしてこれが chokudai さんとの記念すべき最初の会話となりました……）

コード部門では一完でした。A 問題で Nim であることは一瞬で見抜けたのにバグらすこと 40 分、ようやく AC……
順位表を見てみると C の方が解かれていたので、B を 1 秒眺めて C に逃げてボコボコに仕返しを受けて泣いていました。

装置部門は読むのがしんどかったです。「よく分かんねえ、数値直打ちでいいか！w」と思って直打ちしたのですが、まさかの 16 位で決勝進出してしまいました。ごめん……
決勝でも特にうまい方法は思い付かず、シミュレータでのコードのパラメータをちょっと変えただけのコードとなってしまいました。動いている装置を見ながら、「ごめんな……俺のクソコードで動かしてしまって……」と心の中で語りかけていました。

懇親会

うろうろして DDCC ケーキを食べ、装置を眺めてうろうろしてました。

まとめ

初めてのオンサイトでしたが、かなり楽しかったです。今回は 21 卒枠という、たまたま運良く降ってきた機会で参加できただけですが、もっと実力をつけてまた参加できたらなと思います。今回喋っていただいた方、ありがとうございました。またオンサイトでお会いしたいです。
また、コンテストを開催していただいた運営の方々もありがとうございました。

2019-09-10

CF #207 A: Knight Tournament (356A)

セグ木で解けると聞いて解こうとしたけど、無理だったのでセグ木を使わず解いた。

問題概要

問題：
codeforces.com

$1$ 〜 $n$ までの番号が付いた $n$ 人の王様が、勝ち残り形式で勝負をします。勝負は $m$ 回行われます。勝負は順次行われていき、 $i$ 番目の勝負の情報として "戦った王様の中で一番小さい番号が $l_i$ 、大きい番号が $r_i$ 番目であり、王様 $x_i$ が勝ち抜いた" が与えられます。各王様がどの王様に倒されたかを出力してください。優勝した王様に関しては $0$ を出力してください。

解法

セグ木を使うと聞いていたのでセグ木で解こうとしたが、更新時、クエリ時の動きが分からなくて断念した。よくよく考えると、勝負は順番に行われていくので、「 $l_i\le k\le r_i$ なる王様 $k$ が戦う勝負に関して、まだ誰に倒されたかが分かっていないときは王様 $k$ が倒された相手として $x_i$ を記録しておく」ことで誰に倒されたかが分かります。

実際に解くときはsetでまだ誰に倒されたか分かっていない王様を管理しておき、誰に倒されたか分かった時点でsetから除いていく（erase関数を使う）ことでうまく誰に倒されたかが分かります。 $i$ 番目の勝負の勝者である $x_i$ に関してはまだ誰に倒されたかが分からないので、その王様に関してだけスキップすることに注意です。計算量は $O(nlogn)$ です（間違っていたらすみません）

提出：
https://codeforces.com/contest/356/submission/60293084

計算量が間違っていたり、セグ木での解き方が分かる方は教えてください。

2019-09-09

CF #197 D: Xenia and Bit Operations (339D)

コードが汚いのはご愛嬌。

問題概要

$2^n$ 個の要素を持った数列 $a$ が与えられます。 $a_1\ {\rm or}\ a_2, a_3\ {\rm or}\ a_4, \cdots$ として新しい数列 $a'$ を作り、その新しい数列に対して $a'_1\ {\rm xor}\ a'_2, a'_3\ {\rm xor}\ a'_4, \cdots$ として新しい数列 $a''$ を作ります。このように ${\rm or}$ と ${\rm xor}$ を交互に用いて新しい数列をどんどん作っていくと最終的に1つの値が求まります。クエリ「 $a_p$ を $b$ に変える」が $q$ 個与えられるので、各クエリ実行後に得られる値を出力してください。