-
×
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
-
半年ぶりの投稿。
上半期忙しい予定が1年中忙しくなりそう。
ここ2ヶ月くらいでHTMLとかCSSとかJavaScriptとかTypeScriptとかReactとかReduxとか使えるようになってChrome拡張をリリースしたりしてた。
このTwitter・ブログはあまりリアルとは紐付けたくないのでリリースしたものは秘密。
WEB系は初めて触るので色々苦労したけどさすがにWEB系全く触れませんはちょっと頂けないなと思ったよね。
今日は半年ぶりに競技プログラミングの問題を解いた。
もちろんC++。
JavaScript触ってるときはそもそも型という概念がなくてC++の静的型付けが恋しい。
TypeScript触ってるときはJavaScript本来の自由度の高いオブジェクトと相反する無駄に厳しい型付けからC++の適度な静的型付けが恋しい。
そんなことを思いながら勉強していたが、改めてC++触ったらやっぱり不満出るんだろうなぁ。
久々に触ったC++はそんな杞憂は吹き飛ばす書きやすさ・・・。
以下本編。
コード
https://atcoder.jp/contests/abc030/submissions/6923058
ABC030全部解いたうちのD問題。
A問題は"DRAW"と"DROW"を間違えて「は？？？」って何度もWA食らってた。
10^100000とかいう異常事態にどうしようかと為す術がなかった。
10^100000 ≒ 2^332192
BITSET<340000>とか使うのかな？なんて考えて素直にギブアップして解説をちょろっと見た。
なるほどmodは多倍長整数使わなくてもStringから1桁ずつ計算できるのか。
その部分でどうしようもなさすぎてその先はあまり考えていなかったが、ループ部分とループ外の最初の部分に分けて考えるのは思い付けてそう。
その後部分点があったのでとりあえずlong long型に入れてやってみると意外とすんなり部分点が取れたものの、Stringのmodを使うと今まで部分点取れてた部分の一部もWAになるのが非常に困った。
原因はこちら
while (kmod <= first) {kmod += loop;}
最初ループにしておらず、例えばループ外が100、ループが2の場合なんかに、kmodに2を足してもまだループにたどり着かないなんてことが発生する。
たどり着くまで足してあげればいいのだが、少し特殊な実装になってしまったように思う。
私の実装では、ループ外とループ内の値を1つのインデックスで扱っていたが、ループ外とループ内のインデックスを分けてあげれば超えるまでループする作業はいらなさそう。
苦手意識の高いインデックスの0スタートと1スタートについて考えるのが面倒でこうなってしまった。
ここ2ヶ月くらいでWEB系勉強したと書いたが、アルゴリズムを実装しない限りインデックスの開始番号なんてほとんどの場合どちらでも良いので、単純に半年ぶりに苦手な部分を考え直して疲れた。
ちょっとAtCoderの色が役立ちそうな感があるので、また継続的にやっていきたいところ。
1日でD問題ある程度解けるくらいには理解力と実装力がまだあるみたいなのでちょっと安心。
これでB問題で「うぅ・・・」ってなったらどうしようかと思った。PR -
1月中頃からインフルエンザにかかっておりました。
虚弱体質を生かして咳がなかなか治らずに10日ほど家で療養してました。
インフルエンザにかかる前から「期限まで後2週間しかないよーどうしよー」なんてリアル事情で内心焦ってたけど、インフルエンザになるとさすがに吹っ切れて自信が湧いてくる。
5日くらいはPCなんて触れる状況じゃなかったけどそれ以降頑張ったよね。
なんとか仕上げてそれから1月末まで結構詰まってたけど最近やっと落ち着いてきた感じ。
一番得意なC++すら書けるか不安なほど最近プログラムに触っていないけど仕方ない。
ここから競技プログラミングもやっていきたい、ところではあるけれどやっぱり上半期は厳しそう。
しばらく書くこともないなぁ。 -
新年初(記事にする)問題。
コード
https://atcoder.jp/contests/caddi2018b/submissions/3928826
解説見たらだいぶ簡単だけど思いつけない。
問題読んでまずゲーム木の問題なんだろうなぁと考えたけどゲーム木っていう言葉くらいしか知らないからどうしようかと。
結局諦めて解説見たわけだけどたぶん数時間考えても解けてなかったと思う。
今回の学びは、2人が順番に何か操作する問題を解くのコツは自分が完全にコントロールできる部分を把握するべし、ということ。
「1～3までの数字を順番に言って最後に10言ったら勝ちゲーム」でも、自分と相手が言う合計は最小で4にコントロールできることから、4の倍数を考えることが勝つためのコツとなる。
今回の問題だと、「各種1つずつまでしか取れない→各種の2の倍数を考える」と考えればよかったのだろう。
これが3人になるとどうすれば良いのだろうか。
取る数が0か1だとすると、2人の取り方で0～2の範囲がある時点で自分が取れる0,1では全くコントロールできない。
0と3は能動的に避けることができるが、1か2に絞るのが精一杯だろう。
そういう問題が出たらどう解けばいいんだろうか？
再帰で解ける範囲なら解けそうだが、それ以上になると無理だろう。
また別の考え方があるのだろうか。 -
あけましておめでとうございます。毎年年越しは夜中まで起きて昼前から夜まで寝ていたけど、今年は夜中に1時間ほど寝られたので昼過ぎまで起きて夜まで寝ました。夜中もっと寝たかったけど31日に変な時間に寝たせいで寝られなかった残念。テレビで流れていたLiSAの曲で1時間の睡眠から目覚められたので満足です。
今年の目標はAtcoderで赤といきたいところだけど、上半期は忙しそうだからたぶん目指そうと思うことすら難しそう。ということで1個下の橙色目指していきましょう。自分が低い目標を持つとそれで満足しちゃう人間だと知っているからね。Atcoder社長さんの上のツイート曰く初級者は緑目指してね、らしいからだいぶ調子に乗っているけどいいでしょう。何も開発に携わったことないし入門者の可能性まであるが。
後はTwitter活用していきたい。今まで最初の挨拶とpow()関数変なんだけど！？っていう文句の2つしかツイートしてないね。コンテストに参加したら何か呟けそうだし早めに何か参加してみたいところ。
そもそも誰も見ないだろうしどうでもいいやってTwitter載せてなかったから一応リンクを貼っておきます。
https://twitter.com/chlol27
誰も見ないだろうし、とは思っているもののブログ自体の見栄えをよくしたいとは思っています。
そもそも一昨年ブログを始めたモチベーションがHTMLとかCSSとか勉強したい、だからね。
広告も出るの嫌だし今年は時間あればWeb系勉強できそうなもっと色々カスタマイズできるところでやりたい。
C++とPythonとHTMLとCSSとjavascript触れたらとりあえず最強感ない？ないか。
それでは今年もよろしくお願いします。 -
2018年の競技プログラミングの記録を残しておきます。
12月にちょこっと思い出して再開しただけあって数字にするとさすがに全然やってない。
ちなみにyukicoderはアカウント作り直してAtcoderは昔作った奴そのまま使ってます。
