競技プログラミング

next_permutationを久しぶりに使った。

木(グラフ)を作って、dfs。解説そのまま。

解説のソースコードみたいにすっきりとはいかなかったけれど、再帰関数で通りました。

問題 atcoder.jp 考察 原点(0, 0)からユークリッド距離でRずつしか移動できない。 移動先の座標は整数でなくてもよい。 ぴったり(X, Y)にたどり着かなければならない。 これがこの問題を解くときに大事なポイントだと思われる。原点(0, 0)と(X, Y)間のユークリッド距離がRで割り切れる場合は 単純にユークリッド距離をRで割れば何回で(X, Y)にたどり着くか分かる。逆にユークリッド距離がRで割り切れない場合については (X, Y)とのユークリッド距離がR未満になるまで、(X, Y)に向かって移動する。（移動後の座標を(x, y)とする） その後、(x, y)からユークリッド…

ABC198のC問題 Compass Walkingを解説します。 解けたのですが、ミスもしましたし、悲しいくらい時間がかかってしまいました。。。atcoder.jp 2 次元平面上の原点に高橋君がいます。高橋君が 1 歩歩くと、いまいる点からのユークリッド距離がちょうど R であるような点に移動することができます(移動先の座標が整数である必要はありません)。これ以外の方法で移動することはできません。高橋君が点 (X, Y) に到達するまでに必要な歩数の最小値を求めてください。 イメージとしては、直線でできる限りRでまで近づいて、行き過ぎそうになったら遠回りして2回でに着くようにすることを考え…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要歩でちょうど距離歩けるとき，原点からまで最短何歩で行けるか．解説 とします．歩歩くとするとなら到達できないことがわかりますが，なら到達できるでしょうか？到達できそうですがのときには注意が必要で，図に書いてみるとわかるように歩かかります．以上から，のとき歩，のときを満たす最小のが答え．を求めるのに，が小数のままなのは誤差が怖いので両辺2乗してを満たす最小のを求めます．これは二分探索などを用いると高速に求めることができます．解の上限や判定を適当に決めてしまうとオーバーフローするので注意．二分探索の実装が面倒ならをからいい感じの上限まで全探…

Pythonに触れて約4か月経過したので、初めてAtcorderのABC198に参加してみました。 結果は時間内にA, B, Cに回答。初学者にしては良い船出だったと思います。 成長記録としてこれから毎回ブログに残そうかな…(できるかな?) 灰色が当面の目標が茶色なので。えっ…今回の成績じゃ全然ダメなの？ と思いきや、初参加時のリセマラ防止の強い下方補正がかかったようです。 当分の間、以下の方針で勉強しようと思います。 【方針】 ・コンテストに慣れるため、ABCには必ず参加する ・復習は必ず実施して、本番のハマったポイントは必ず明確化する ・継続が力になると信じて、毎日必ず1問演習する 以下が…

更新日時 2021/04/14/07:00 Qiita Trends Daily 1位 [New] CSS,JavaScript,GitHub,翻訳,フロントエンド Qiita Trends Daily 2位 ※前日1位 JavaScript,TypeScript,React,コンポーネント,props Qiita Trends Daily 3位 ※前日7位 プログラミング,初心者,レビュー,初心者向け,新人プログラマ応援 Qiita Trends Daily 4位 ※前日4位 JavaScript,TypeScript,ゲーム制作,pixi.js,Vue.js Qiita Trends Da…

4/5で僕は25歳になった 4/1からは社会人3年目となった。2年前の今日はプログラミングのプの字も知らなかったのに割と意欲的に取り組めたんじゃないかと思う。 業務では、通信分野・組み込み開発をしている プライベート * 社会人1年目では、ディープラーニング・機械学習から初めて、競技プログラミングにハマりAtCoderでは緑になった。(下から３番目レベル, 上位30%くらい) * 社会人2年目では、スマホアプリ開発(Android)、Web開発（フロントエンド、バックエンド）、自宅サーバー設置など ただ技術は全てが中途半端だ。 しかし、全てを満遍なく知ることができた。 これからのキャリアを考え…

１ヶ月前の自分が読んだら意味が分からないタイトルです。 過去の自分に向けて説明するならば、「競技プログラミングの勉強（界隈では精進と言うのが慣例）の記録を、GitHubというコードのバージョン管理システムに上げてcontribution（変更回数）に応じてヒートマップで示したものを作りました」といったところでしょうか。 iOSのウィジェットでこのcontributionのグラフが見れるので、ホーム画面に設定して毎日眺めています。 私のcontributionグラフ（まばらに草生えた） 自分は学ぶ楽しさそのものではすぐに熱が冷めてしまう無精者なのですが、記録してモチベーションを上げることでなんと…

04/05(月) 午前9時半起床。 二度寝するべきだとは思っていたが、寝落ちする前に読んでいたノクターンノベルズの続きを読み始めてしまい、そのまま止まらなかった。正午、読了。 https://novel18.syosetu.com/n7640gf/ 主人公とハーレムメンバーのバランスのとり方とか、主人公の優しさが良さげに描かれていて良かった。 そのまま他の作品を漁って、2つ読んだ。こちらは完全にエロに振り切っていてストーリーなどないようなものなので、特に感想もない。題名も書かないので気になる人はリンク先（R18サイト）に飛んでほしい。 https://novel18.syosetu.com/n…

！！！初めまして！！！ 今日からブログを始めました。伊茂木拓尾です。 本題と関係ないので自己紹介は興味がないと思います。なので、簡潔にしますと、関西出身、Fラン文系大学生2回生、童貞オタクです。ブログ初心者なので、至らない点もあると思いますが、ご了承ください。 さっそく本題に入りますが、皆さんは ”競技プログラミング” というものをご存じでしょうか？ 一般的な文系大学生なら、知らないのも当たり前だと思います。かく言う僕も、つい最近知りました。 競技プログラミングとは！！！ 参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。wikipedia…

https://atcoder.jp/contests/abc198/tasks/abc198_e 前提知識 dfs 解説 https://atcoder.jp/contests/abc198/submissions/21691565 競技プログラミングの問題で木を題材とした問題が多く存在する。 どのようにプログラミングするとよいかは人それぞれかと思うが、隣接グラフを使って頑張ることを勧める。 dfs 今回の問題は木構造のとある根（頂点1）からのある条件を使っている。 よって、頂点1を始点としてdfsすることでうまく扱えるような感じに見える。 cnt[color] := 色colorがこれまで…

みなさん初めまして。naturenceと申します。普段は大学で動物の研究をしています。最近、「なんとなくかっこよさそう」という適当な動機でプログラミング（主にPython🐍）の勉強を始めました。特に競技プログラミングにハマっており、現時点でのAtCoderのレートは518（茶色）です。 このブログでは、 アルゴリズムを定着させるための知識の整理（＋コードの備忘録） コンテストの感想・復習 をメインに書いていく予定です。その他、新しいことにチャレンジしていく際にはその記録も書いていきたいです。 どうぞよろしくお願いいたします。

はじめに 競技プログラミングに関連する、以下の記事が話題にあがりました。nuc氏1つ目の記事 nuc.hatenadiary.orgchokudai氏の記事 chokudai.hatenablog.comnuc氏2つ目の記事 nuc.hatenadiary.orgnuc氏は、元Googleのエンジニアで面接も担当されていました。現在は某医大の特別特命准教授の方で、2007年頃に東大で競技プログラミングをされていた方のようです（氏名も役職も上記の記事のリンク先で公表されています）。nuc氏の記事は、競技プログラミングに対して「我々の目的の一つは、我々が始めてしまった競技プログラミングを我々が終わ…

こんにちは。MIS.W終身名誉幽霊サークル員、サークル活動に現れた回数は2年間で片手で数えるほどのSen(@nonpro3)と申します。競技プログラミングやアルゴリズムに興味があり、最近はソフトウェア開発にも精を出しています。本日はAndroidやったことのない人がAndroidアプリ開発でバイトorインターンで採用できるまでの大まかなガイドラインを書こうと思います。 Android開発での代表作は理工展パンフレットアプリです。(理工展連絡会はいいですぞ！こちらも兼サー歓迎、年会費無料なので文化祭運営やりたい人は来てねー！) ちなみにこんな幽霊度が高くて他のサークルのスパイでもMIS.Wの新歓…

こんにちは。仮の人と申します。 唐突ですが私は東北大学競プロサークルのpuzzleknotの一員として日々競プロに励んでいます。競プロ楽しい!!という思いで活動しているわけですが自分がしていて楽しいことは共有したいやん?ということで競プロの紹介をしたいと思います。 大学に入ったり新たな学年になったりして新たな事を始めたいなと思案している人に届けばいいなと思っております。 競プロって何ぞや? そもそも競プロというものをご存じでしょうか。 競プロは正式には競技プログラミングと言います。競技+プログラミングという名前通り、プログラミングに競技性を加えたものです。 競い方には様々な種類があります。最も…

PCTです。AtCoder黄色になることができました！ PCTprobabilityさんのAtCoder Beginner Contest 196での成績：162位パフォーマンス：2271相当レーティング：1999→2030 (+31) :)Highestを更新し、初段になりました！#AtCoder #ABC196 https://t.co/Vdq5PYz5Xx 黄色になりました！！！！！！！！ABC卒業！！！！！！うれしい！！！！！！！！！ pic.twitter.com/TvIYRc5heI — PCT (@PCTprobability) 2021年3月20日 色変記事です。色々書きます。…

はてなブログ独自の集計による人気記事のランキング。3月28日（日）から4月3日（土）〔2021年4月第1週〕のトップ30です*1。 # タイトル／著者とブックマーク 1 Twitter で医師を拾ってきて Google のソフトウェアエンジニアにするだけの簡単なお仕事 - 白のカピバラの逆極限 S.144-3 by id:nuc 2 競技プログラミングの在り方 ～「競技プログラミングを我々が終わらせる」を受けて～ - chokudaiのブログ by id:chokudai 3 pipとpipenvとpoetryの技術的・歴史的背景とその展望 - Stimulator by id:vaaaaaa…